Solution
本题还有一个弱化版，见Luogu P1775
我们发现本题和弱化版唯一区别就是本题有环。
我们先将弱化版的内容。
Easy version
Description
弱化版是给定了好多堆石子，每相邻的两堆可以合并成一个大堆，每次合并会产生两个石头重量和的价值，最后会将若干堆石子合并为一堆。求如何合并会使最后价值最大。
Solution
首先，本题和合并果子不同的是，本题必须两个相邻的堆合并，而合并果子是随意合并，所以可以扔进优先队列里贪心。而本题显然不能贪心。
考虑dp，本题显然有大的组和小的组，大的组里包含小的组，考虑区间dp。
我们定义\(f_{i,j}\)表示区间\(i,j\)合并完最大的价值，由于是合并完的，我们不知道是由哪两个区间合并，所以需要枚举分割点。最后记得加上合并两个区间的价值。
为了在O(1)的时间复杂度内求出合并两个区间的价值，我们可以预处理前缀和，这里不再赘述，下文状态转移方程及代码默认\(sum_i\)表示前\(i\)堆价值总和。
若定义分割点为\(k\)，则状态转移方程：\(f_{i,j}=max(f_{i,j},f_{i,k}+f_{k+1,j}+sum_j-sum_{i-1})\)
explanation：两个区间分别的价值+合并这两个区间的价值
再考虑枚举顺序问题。
首先枚举区间长度len，再枚举左区间，有了len和左区间显然就可以确定右区间，确定完区间后再枚举分割点\(k\)。因为只有这样才能确保枚举到大区间的时候可以利用小区间。因此要优先确保len是按照顺序枚举的。
至此，本题得解，代码如下：
Code
/*
区间dp
显然每次一定是两堆小的合成一个大的，转移也一定是从小的转移到大的。
如何转移？也就是如何表示小的？
我们可以把大的拆分成两个小的。
具体怎么拆分？循环枚举每种拆分方式然后取min
三层循环，先枚举长度，然后枚举left，这样我们就得到了left和right，再枚举拆分点即可。
状态设计：f[l][r]表示区间为l-r的石子合并所需要的最小代价。
状态转移方程显然：f[l][r]=min(f[i],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]
我们这里用了前缀和预处理，确保在O(1)的复杂度下求和
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1000
#define INF 0x3f3f3f3f
using namespace std;
int a[N];
int sum[N];
int n;
int f[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) sum[i] = sum[i-1]+a[i]; //预处理前缀和
for(int len=2;len<=n;len++)
{
for(int i=1;i<=n-len+1;i++)
{
int l = i,r = i+len-1;
f[l][r] = INF;
for(int k=l;k<r;k++)
{
f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
}
}
}
cout<<f[1][n]<<endl;
return 0;
}
Normal version
Description
上文提到，Hard version和弱化版的唯一区别是一群堆围成了环。因此，我们需要拆换为链，具体处理是使得\(a_{n+i}=a_i\) ,也就是使环的前后拼成了一条链，其余的按照Easy Version处理即可。拆环为链的具体操作见代码。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int n;
char c[N];
int a[N];
int f[N][N],g[N][N];//f数组处理最大，g数组处理最小
int sum[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n] = a[i];
}
for(int i=1;i<=(n<<1);i++)sum[i]=sum[i-1]+a[i];//预处理前缀和
for(int len=2;len<=(n<<1);len++)
{
for(int l=1,r=len;r<=(n<<1);l++,r++)
{
for(int k=l;k<r;k++)
{
f[l][r] = max(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
g[l][r] = min(g[l][r],g[l][k]+g[k+1][r]+sum[r]-sum[l-1]);
}
}
}
int ans = -INF,ans1 = INF;;
for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]),ans1 = min(ans1,g[i][i+n-1]);
cout<<ans1<<endl<<ans<<endl;
return 0;
}
拓展延申
此类合并石子模型还有一个Hard Version。
题面看着又臭又长，随着读题，我们可能会发现一些Hint
选择一条边连接的两个顶点V1和V2，用边上的运算符计算V1和V2得到的结果来替换这两个顶点。
等等，“替换” 这不就是合并！去掉一条边实际就是决策，于是，我们成功将这道远古IOI题转换成了合并石子模型。
但是，我们需要注意的是，本题牵扯到乘法，可能出现“负负得正”的情况，因此我们还需要记录一下最小值，然后做乘法运算的时候分类讨论取max，至于加法操作按照合并石子模型操作即可。
另外，本题仍然有环，需要和合并石子 Normal Version一样拆环为链，具体操作在上文已经详解，这里不再赘述。
具体实现见代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int n;
char c[N];
int a[N];
int f[N][N],g[N][N];
int main()
{
scanf("%d\n",&n);
for(int i=1;i<=n;i++)
{
cin>>c[i]>>a[i];
getchar();
c[i+n] = c[i];
a[i+n] = a[i];
}
for(int i=1;i<=(n<<1);i++)
{
for(int j=1;j<=(n<<1);j++)
{
f[i][j] = -INF;
g[i][j] = INF;
} //
}
for(int i=1;i<=(n<<1);i++) f[i][i]=g[i][i] = a[i];
for(int len=2;len<=n;len++)
{
for(int l=1,r=len;r<=(n<<1);l++,r++)
{
// int r = l+len-1;
// f[l][r] = -INF;
// g[l][r] = INF;
for(int k=l;k<r;k++)
{
if(c[k+1] == 'x')
{
f[l][r]=max(f[l][r],max(f[l][k]*f[k+1][r],max(g[l][k]*g[k+1][r],max(f[l][k]*g[k+1][r],g[l][k]*f[k+1][r]))));//列举全
g[l][r] = min(g[l][r],min(f[l][k]*g[k+1][r],min(g[l][k]*g[k+1][r],min(f[l][k]*g[k+1][r],g[l][k]*f[k+1][r])))); //列举全
}
else if(c[k+1] == 't')
{
f[l][r] = max(f[l][r],f[l][k]+f[k+1][r]); //加法正常操作即可
g[l][r] = min(g[l][r],g[l][k]+g[k+1][r]);
}
}
}
}
int ans = -INF;
for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);
printf("%d\n",ans);
for(int i=1;i<=n;i++)if(f[i][i+n-1]==ans)printf("%d ",i);
return 0;
return 0;
}