玄关

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int N;
int a[250];
int sum[300];
int dp1[250][250],dp2[250][250];
int dfs1(int l,int r)
{
    if(dp1[l][r]) return dp1[l][r];
    if(l==r || l>r) return dp1[l][r]=0;  //加上l>r只是为了少讨论
    int ans=INT_MAX;
    for(int i=l;i<r;i++)
        ans=min(ans,dfs1(l,i)+dfs1(i+1,r)+sum[r]-sum[l-1]);   //合并两个区间所需+合并最终的石头所需，即l~r内所有石头之和
    return dp1[l][r]=ans;
}
int dfs2(int l,int r)
{
    if(dp2[l][r]) return dp2[l][r];
    if(l==r || l>r) return dp2[l][r]=0;  //加上l>r只是为了少讨论
    int ans=-1;
    for(int i=l;i<r;i++)
        ans=max(ans,dfs2(l,i)+dfs2(i+1,r)+sum[r]-sum[l-1]);   //合并两个区间所需+合并最终的石头所需，即l~r内所有石头之和
    return dp2[l][r]=ans;
}
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++) cin>>a[i];
    sum[1]=a[1];
    for(int i=1,j=1;i<=2*N;i++,j++)
    {
        if(i>N) j%=N;
        sum[i]=a[j]+sum[i-1];   //区间扩大两倍
    }
    int minans=INT_MAX,maxans=-1;
    for(int i=1;i<=N;i++)
    {
        for(int j=i+1;j<=N+i;j++)   //分成i~j-1,j~i+N-1两个线性区间（i'==j，即j=N+i时包含(i~~j-1)整个区间）
        {
            minans=min(minans,dfs1(i,j-1)+dfs1(j,i+N-1)+sum[N]);  //别忘加上总和
            maxans=max(maxans,dfs2(i,j-1)+dfs2(j,i+N-1)+sum[N]);
        }
    }
    cout<<minans<<endl<<maxans-sum[N];
}