hdu3506(dp四边形优化)

本文主要是介绍hdu3506(dp四边形优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：点击打开链接

题意：求环形石子合并

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int s[2005][2005],dp[2005][2005],sum[2005][2005];
int main(){                                     //区间dpint n,i,j,k,l,ans;                          //m(i,j)=min{(m(i,k-1)+m(k,j)+w(i,j)}(i<k<=j)while(scanf("%d",&n)!=EOF){                 //当i<i'<j<j'并且memset(dp,INF,sizeof(dp));              //w(i,j)+w(i',j')≤w(i',j)+w(j,i')时for(i=1;i<=n;i++){                      //函数m也满足这个关系，从而可以用四边形优化scanf("%d",&sum[i][i]);             //也就是k的范围在s(i,j+1)~s(i+1,j)内sum[i+n][i+n]=sum[i][i];            //s(i,j)代表函数m(i,j)对应的决策变量的最大值dp[i][i]=dp[i+n][i+n]=0;            //具体证明看论文:s[i][i]=i,s[i+n][i+n]=i+n;          //http://wenku.baidu.com/view/be418243a8956bec0975e3bf.html?re=view}for(i=1;i<=2*n;i++)for(j=i+1;j<=2*n;j++)sum[i][j]=sum[i][j-1]+sum[j][j];for(l=2;l<=2*n;l++){for(i=1;i<=2*n-l+1;i++){j=i+l-1;for(k=s[i][j-1];k<=s[i+1][j];k++){if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[i][j]){dp[i][j]=dp[i][k]+dp[k+1][j]+sum[i][j];s[i][j]=k;}}}}ans=INF;for(i=1;i<=n;i++)ans=min(ans,dp[i][i+n-1]);printf("%d\n",ans);}return 0;
}

这篇关于hdu3506(dp四边形优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---