动态规划之四边形不等式和斜率优化

《动态规划之四边形不等式和斜率优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1四边形不等式优化对于转移如果满足：存在s[i][j]的转移：最后转移：1.1例题：hdu3480划分问题DivisionProblemDescriptionLittleDisreallyinterestedinthetheoremofsetsrecently.There’saproblemthatconfusedhimalongtime.  LetTbeasetofintegers.LettheMINbetheminimumintegerinTandMAXbethemaximum,thenthecostofset

2、Tifdefinedas(MAX–MIN)^2.NowgivenanintegersetS,wewanttofindoutMsubsetsS1,S2,…,SMofS,suchthatandthetotalcostofeachsubsetisminimal.InputTheinputcontainsmultipletestcases.Inthefirstlineoftheinputthere’sanintegerTwhichisthenumberoftestcases.ThenthedescriptionofTtes

3、tcaseswillbegiven.Foranytestcase,thefirstlinecontainstwointegersN(≤10,000)andM(≤5,000).NisthenumberofelementsinS(maybeduplicated).Misthenumberofsubsetsthatwewanttoget.Inthenextline,therewillbeNintegersgivingsetS.OutputForeachtestcase,outputonelinecontainingexa

4、ctlyoneinteger,theminimaltotalcost.Takealookatthesampleoutputforformat.SampleInput2321244247101SampleOutputCase1:1Case2:1分析：1）dp[i][j]表示前i个数字，分成j份的最小值2）dp[i][j]=min(dp[k][j-1]+w[k+1][j])(i<=k

5、e#include#includeusingnamespacestd;#defineN10001#defineM5001constintINF=0x7fffffff;inlineintsqr(intx){returnx*x;}intn,m;inta[N];intdp[N][M];ints[N][M];intcal(){if(n<=m)return0;sort(a+1,a+1+n);for(inti=0;i<=n;++i)for(intj=0;j<=m;++j)

6、dp[i][j]=-1;dp[0][0]=0;for(inti=1;i<=n;++i){intmaxj=min(i,m);intmn=INF,mk;for(intk=0;k=1;--j){intmn=INF,mk;for(intk=s[i-1

7、][j];k<=s[i][j+1];++k)if(dp[k][j-1]!=-1){inttmp=dp[k][j-1]+sqr(a[i]-a[k+1]);if(tmp

8、Case%d:%d",++cas,cal());}return0;}1.2例题hdu3506合并问题MonkeyPartyProblemDescriptionFarawayfromourworld,thereisabananaforest.Andmanylovelymonkeyslivethere.Oneday,SDH(SongDaHou),whoist