题意

• 给定n堆石子，成环放置，每堆石子有自己的重量，每次合并可以合并相邻的两堆，合并的得分是两堆石子重量和，求解把所有石子合并成一堆所得的最大得分和最小得分

思路

• 由于两堆石子是相邻的，所以每一次合成其实是对一个区间中的两堆的分界做考虑，下面按求最大得分考虑，如一共1~5，合并1~5的最后一次等价于将1~5拆分成两堆的不同分界的不同价值{[1|2,3,4,5],[1,2|3,4,5],[1,2,3|4,5],[1,2,3,4|5]}并取最大
• 由此得到状态转移方程(k属于l~r-1)
• 特别的，因为题目中说是环形放置，我们将原序列倍增，即可枚举出环的每种情况，具体来讲就是dp数组得开两倍长
• 初值：由于转移方程加入了合并时区间的和，所以当区间长度为1时，dp的值应该是0，才能保证在更新区间长度为2的dp值正确，即 ，又因为后面更新最大最小值的时候涉及取max和取min，所以剩余的空间赋值为{max:0|min:0x3f3f3f3f}

补充：处理环的第二种方法

• 规定环断开的位置，考虑断开后的影响，如串成环选择n个区间，变为第一个区间必须选头，最后一个区间必须选尾，选择n+1个区间，然后再和不同时选头尾，选择n个区间的答案作比较

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N =600;
int a[N],sum[N];
int dp1[N][N];
int dp2[N][N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(dp2,0x3f3f3f3f,sizeof(dp2));
    int n;
    cin >> n ;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        a[i+n]=a[i];
        dp2[i][i]=0;
        dp2[i+n][i+n]=0;
    }

    for(int i=1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=n;len++){
        for(int l=1,r=l+len-1;r<=2*n;l++,r++){
            for(int k=l;k<=r-1;k++){
                dp1[l][r]=max(dp1[l][r],dp1[l][k]+dp1[k+1][r]+sum[r]-sum[l-1]);
                dp2[l][r]=min(dp2[l][r],dp2[l][k]+dp2[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    int ans_max=0,ans_min=INT_MAX;
    for(int i=1;i+n-1<=2*n;i++){
        ans_max=max(ans_max,dp1[i][i+n-1]);
        ans_min=min(ans_min,dp2[i][i+n-1]);
    }
    // for(int i=1;i<=2*n;i++){
    //     for(int j=1;j<=2*n;j++){
    //         cout << dp2[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    cout << ans_min << endl;
    cout << ans_max << endl;
    return 0;
}