（鉴于题面直接复制过来太丑，这里就直接放链接了）
题目：
大概思路：
（我就是个智障）
每次写dp，都会在得出正确状态转移方程的边缘反复横跳，然后卡死在上面。（nmdwsm）
这次同样。。。。可能是今天物理学傻了，在反复思考怎么求出dp[i][k]和dp[k][j]。。。。
后来看了石子合并才幡然醒悟。。原来之前的状态列出来就好不要考虑啊。。。。。
之前的状态在当前看来是已知量啊！！！！！！！
以后不要卡在这种沙雕的地方了啊啊啊啊！！！！！
其实这道题的思路比之前写的释放囚犯要简单不少，就是石子合并换了个衣服而已。。
就是在细节处理上要稍微注意一点。。。复制数组的时候不要把下标存进去了。。（真-脑子不在家）
细节问题写在注释里了
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int a[202],dp[202][202];
int n;
void read(int &x)
{
char c=0;
x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c))
x=x*10+c-'0',c=getchar();
}
int maxx;
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i]);
a[i+n]=a[i];
}
for(int p=2;p<=n+1;p++)//这里最少也要有两颗珠子才可以合并
{
for(int i=1;i+p-1<=2*n;i++)//注意边界，最后一颗珠子的尾标在第一颗珠子上
{
int ends=i+p-1;
for(int k=i+1;k<ends;k++)//不能从头切
dp[i][ends]=max(dp[i][ends],dp[i][k]+dp[k][ends]+a[i]*a[k]*a[ends]);//两个区间一定是接上的
}
}
for(int i=1;i<=n;i++)
{
maxx=max(maxx,dp[i][i+n]);//同石子合并
}
cout<<maxx<<endl;
return 0;
}
只可以看注释哦。。
掰掰
CSP-S RP+++!