https://www.cnblogs.com/violet-acmer/p/9852294.html
题解：
这道题是石子合并问题稍微升级版
这道题和经典石子合并问题的不同在于，经典的石子合并问题是一排，而此问题是一个圈，也就意味着最后一堆石子可已选择第一堆石子，那这要怎么做呢？
其实方法很简单，在n堆石子后额外增加(n-1)堆石子，这(n-1)堆石子不是随意造的，其个数与前(n-1)堆石子一一对应。
然后，就是经典的石子合并问题了。
对于 1 到 2*n-1堆石子，进行区间最优解的查找即可。
详情请看大佬博客：https://blog.csdn.net/u013512086/article/details/54565572
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=+; int n;
int a[maxn];
int dp[maxn][maxn];//dp[i][j]:讲区间[i,j]堆石子合并所需的最小（或大）的花费
int sum[maxn];//前缀和 void Solve()
{
//求解最小花费
mem(dp,INF);
for(int i=;i <= *n;++i)
dp[i][i]=;
for(int len=;len <= n;++len)
{
for(int i=;i <= *n-len;++i)
{
int j=i+len-;
for(int k=i;k < j;++k)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]+sum[j]-sum[i-]);
}
}
int minRes=INF;
for(int i=;i <= n;++i)
minRes=min(minRes,dp[i][i+n-]);
printf("%d\n",minRes);
//求解最大花费
mem(dp,);
for(int len=;len <= n;++len)
{
for(int i=;i <= *n-len;++i)
{
int j=i+len-;
for(int k=i;k < j;++k)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]+sum[j]-sum[i-]);
}
}
int maxRes=;
for(int i=;i <= n;++i)
maxRes=max(maxRes,dp[i][i+n-]);
printf("%d\n",maxRes);
}
int main()
{
scanf("%d",&n);
mem(sum,);
for(int i=;i <= n;++i)
scanf("%d",a+i),a[n+i]=a[i];
for(int i=;i <= *n;++i)
sum[i]=sum[i-]+a[i];
Solve();
}