石子合并

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int a[N];
int sum[N];
int fmx[N][N];//区间l~r的最大得分
int fmn[N][N];//区间l~r的最小得分
int main()
{
    int n;
    cin>>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 len=2;len<=2*n;len++)
    {
        for(int l=1;l<=2*n-len+1;l++)
        {
            int r=len+l-1;fmn[l][r]=1e9+4;
            for(int k=l;k<r;k++)//合并l~k,k+1~r
            {

                fmx[l][r]=max(fmx[l][r],fmx[l][k]+fmx[k+1][r]+sum[r]-sum[l-1]);
                fmn[l][r]=min(fmn[l][r],fmn[l][k]+fmn[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    int ans1=1e9+4,ans2=0;
    for(int i=1;i<=n;i++)
    {
        ans1=min(ans1,fmn[i][i+n-1]);
        ans2=max(ans2,fmx[i][i+n-1]);
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}