链接：https://www.luogu.org/problemnew/show/P1880
思路：再次接触区间dp，这次感觉比第一次理解更深入了一些，一般的线性dp是从前往后递推，但有些情形是需要从左右两个小区间合并为一个大区间，这时候就是区间合并问题了，石子合并是最经典的区间合并问题，区间dp首先枚举区间长度，从2开始（1没有意义且会影响最终结果），然后枚举左端点，然后得出右端点，最后枚举中间断层的地方（k表示在第k个数后断开）。对于环形，我们可以把环拆成长度2倍的链，只需要枚举一下链的起点就可以得到换上所有答案的最值。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
const int maxn = 210;
int a[maxn];
ll maxv[maxn][maxn];
ll minv[maxn][maxn];
ll sum[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[n+i] = a[i];//拆环为链
}
for(int i=1;i<=2*n;i++){
sum[i] = sum[i-1]+a[i];
}
for(int i=1;i<=2*n;i++){
for(int j=1;j<=2*n;j++){
minv[i][j] = 1e18;
}
}
for(int i=1;i<=2*n;i++)maxv[i][i] = minv[i][i] = 0;
for(int len=2;len<=2*n;len++){//从2开始枚举长度（包含左端点本身）
for(int l=1;l+len-1<=2*n;l++){//枚举左端点
int r = len+l-1;//得出右端点
for(int k=l;k<r;k++){//枚举断点（在k的右边断开）
maxv[l][r] = max(maxv[l][r],maxv[l][k]+maxv[k+1][r]);
minv[l][r] = min(minv[l][r],minv[l][k]+minv[k+1][r]);
}
//补上合并代价
maxv[l][r]+=sum[r]-sum[l-1];
minv[l][r]+=sum[r]-sum[l-1];
}
}
ll res1 = 0,res2 = 1e18;
for(int i=1;i<=n+1;i++){//找到环上所有方案的最值
res1 = max(res1,maxv[i][i+n-1]);
res2 = min(res2,minv[i][i+n-1]);
}
printf("%lld\n%lld\n",res2,res1);
return 0;
}
