算法提高之能量项链
-
核心思想：区间dp
-
通过观察发现可以将n个珠子最后的n+1个数看作石子 合并石子
-
-
在l~r的范围内 找k作隔断
-
-
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 110,M = N<<1;int f[M][M];int w[M];int n;int main(){cin>>n;for(int i=1;i<=n;i++) cin>>w[i],w[i+n] = w[i]; //成链memset(f,-0x3f,sizeof f); //求最大初始化最小for(int len = 2;len <= n+1;len++) //区间长度{ for(int l=1,r;r = l+len-1,r<=n<<1;l++) //遍历左端点{if(len == 2) f[l][r] = 0; //说明只有一个珠子else{for(int k=l+1;k<r;k++) //k != l不能相同{f[l][r] = max(f[l][r],f[l][k] + f[k][r] + w[l]*w[r]*w[k]);}}}}int res=0;for(int l=1;l<=n;l++)res = max(res,f[l][l+n]); //每个点都可能是起点cout<<res<<endl;}
