题解 | #石子合并#

#include<bits/stdc++.h>

using namespace std;

const int N=410;
int dpmin[N][N];
int dpmax[N][N];
int a[N];
int n;
int sum[N];

int main()
{
    memset(dpmin,0x3f,sizeof(dpmin));
    memset(dpmax,0,sizeof(dpmax));
    cin >> n;
    int i;
    for(i=1;i<=n;i++){
        cin >> a[i];
    }
    for(i=n+1;i<=2*n;i++){
        a[i]=a[i-n];
    }
    for(i=1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    int k,j;
    for(i=1;i<=2*n;i++){
        for(j=i;j>=1;j--){
            if(i == j) {
                dpmin[j][i]=dpmax[j][i]=0;
            }
            for(k=j;k<i;k++){
                dpmin[j][i]=min(dpmin[j][i],dpmin[j][k]+dpmin[k+1][i]+sum[i]-sum[j-1]);
                dpmax[j][i]=max(dpmax[j][i],dpmax[j][k]+dpmax[k+1][i]+sum[i]-sum[j-1]);
            }
        }
    }
    int ansmin=1e9,ansmax=-1;
    for(i=1;i<=n-1;i++){
        ansmin=min(ansmin,dpmin[i][i+n-1]);
        ansmax=max(ansmax,dpmax[i][i+n-1]);
    }
    cout << ansmin << endl;
    cout << ansmax << endl;
}