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

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

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

2、AX–MIN)^2.NowgivenanintegersetS,wewanttofindoutMsubsetsS1,S2,…,SMofS,suchthatandthetotalcostofeachsubsetisminimal.InputTheinputcontainsmultipletestcases.Inthefirstlineoftheinputthere’sanintegerTwhichisthenumberoftestcases.ThenthedescriptionofTtestcaseswillbegiven.Foranytest

3、case,thefirstlinecontainstwointegersN(≤10,000)andM(≤5,000).NisthenumberofelementsinS(maybeduplicated).Misthenumberofsubsetsthatwewanttoget.Inthenextline,therewillbeNintegersgivingsetS.OutputForeachtestcase,outputonelinecontainingexactlyoneinteger,theminimaltotalcost.Takealo

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

5、acestd;#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)dp[i][j]=-1;dp[0][0]=0;for(inti=1;i<=n;++i){intmaxj=min(i,m);intmn=INF

6、,mk;for(intk=0;k=1;--j){intmn=INF,mk;for(intk=s[i-1][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

7、n){mn=tmp;mk=k;}}dp[i][j]=mn;s[i][j]=mk;}}return(int)dp[n][m];}intmain(){intt,cas=0;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(inti=1;i<=n;++i)scanf("%d",&a[i]);printf("Case%d:%d",++cas,cal());}return0;}1.2例题hdu3506合并问题MonkeyPartyProblemDescriptionFarawayfromourwor

8、ld,thereisabananaforest.Andmanylovelymonkeyslivethere.Oneday,SDH(SongDaHou),whoist