CodeVS/3002

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
石子归并3	★☆☆☆☆	答案正确	100	2014/11/20 8:16:04	无

题意

较大范围的石子归并。

题解

参见CodeVS/1048。

代码

3002.cpp代码已折叠 展开折叠内容

#include<cstdio> #define INF (1<<30) int dp[5000][5000]={},K[5000][5000]={},n,a[5000]={},sum[5000]={}; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; K[i][i]=i; } for (int len=2;len<=n;len++) for (int i=1;i<=n-len+1;i++) { int j=i+len-1; dp[i][j]=INF; for (int k=K[i][j-1];k<=K[i+1][j];k++) if (dp[i][k-1]+dp[k][j]+sum[j]-sum[i-1]<dp[i][j]) { dp[i][j]=dp[i][k-1]+dp[k][j]+sum[j]-sum[i-1]; K[i][j]=k; } } printf("%d",dp[1][n]); return 0; }