首页 > 代码库 > 区间DP基础——石子归并
区间DP基础——石子归并
http://acm.nyist.net/JudgeOnline/problem.php?pid=737
石子归并：先枚举要合并的区间长，然后枚举相应的区间左端点，最后枚举区间中间的划分点，这样，就可以由小到大递推解决区间问题了。
转移方程：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])
1 #include<iostream> 2 #include<cstdio> 3 #define INF 70232024 4 using namespace std; 5 int n; 6 int f[300][300]; 7 int a[300]; 8 int sum[300]; 9 int main()10 {11 while(~scanf("%d",&n) && n)12 {13 for(int i=1;i<=n;i++)14 {15 f[i][i]=0;16 scanf("%d",&a[i]);17 sum[i]=sum[i-1]+a[i];18 }19 for(int l=2;l<=n;l++)20 {21 for(int i=1;i<=n-l+1;i++)22 {23 int j=i+l-1;24 f[i][j]=INF;25 for(int k=i;k<=j;k++)26 {27 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);28 }29 }30 }31 cout<<f[1][n]<<endl;32 }33 return 0;34 }
区间DP基础——石子归并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。