CodeVS/1154 2014年11月26日 (三) 17:19云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
能量项链	★☆☆☆☆	答案正确	100	2014/11/26 17:07:33	无

题意

环形石子归并问题。

题解

石子归并的变题了，环形石子归并其实只要复制一遍接在后面，按照石子归并做就是了，例如：

1 2 3 4 5  ->  1 2 3 4 5 1 2 3 4

DP方程也是类似的：

    dp[i][j]=max{dp[i][k-1]+dp[k][j]+h[j+1]*h[i]*h[k]};

代码

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

#include<cstdio> #include<climits> #include<algorithm> int dp[5000][5000]={},n,h[5000]={},sum[5000]={},n0,Ans=0; int main() { scanf("%d",&n0); for (int i=1;i<=n0;i++) { scanf("%d",&h[i]); h[i+n0]=h[i]; } n=(n0<<1)-1; for (int len=2;len<=n0;len++) for (int i=1;i<=n-len+1;i++) { int j=i+len-1; for (int k=i+1;k<=j;++k) if (dp[i][k-1]+dp[k][j]+h[j+1]*h[i]*h[k]>dp[i][j]) dp[i][j]=dp[i][k-1]+dp[k][j]+h[j+1]*h[i]*h[k]; } for(int i=1;i<=n0;++i) Ans=std::max(Ans,dp[i][i+n0-1]); printf("%d",Ans); return 0; }