洛谷P1880 [NOI1995]石子合并

链接：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;
}