玄关求条

-62
54

#include<bits/stdc++.h>
#define file() ios::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define inf 0xfffff
//#define int long long
using namespace std;

const int maxn=105;
int a[maxn*2];
int c[maxn*2];
int dp[maxn*2][maxn*2];
int dp1[maxn*2][maxn*2];

signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        c[i]=c[i-1]+a[i];
        a[i+n]=a[i];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n*2-len;i++){
            int j=len+i-1;
            dp1[i][j]=inf;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
                dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]);
            }
            dp[i][j]+=c[j]-c[i-1];
            dp1[i][j]+=c[j]-c[i-1];
        }
    }
    int ans=0,ans1=inf;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i][i+n-1]);
        ans1=min(ans1,dp1[i][i+n-1]);
    }
    cout<<ans1<<"\n"<<ans;
    return 0;
}