深搜

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
int n,nn,ans=1000000000;
int a[405];
int sum[405];
int dp[405][405];
void init(int s,int e)
{
	for(int i=1;i<=nn;i++)
		for(int j=1;j<=nn;j++)
			dp[i][j]=-1;
	for(int i=s-1;i<=e;i++)
		sum[i]=0;
	for(int i=s;i<=e;i++)
		sum[i]=sum[i-1]+a[i];
}
int dfs(int l,int r)
{
	if(dp[l][r]!=-1)
		return dp[l][r];
	if(l==r)
		return dp[l][r]=0;
	dp[l][r]=1000000000;
	for(int i=l;i<r;i++)
		dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i+1,r)+sum[r]-sum[l-1]);
	return dp[l][r];
}
int ddfs(int l,int r)
{
	if(dp[l][r]!=-1)
		return dp[l][r];
	if(l==r)
		return dp[l][r]=0;
	for(int i=l;i<r;i++)
		dp[l][r]=max(dp[l][r],ddfs(l,i)+ddfs(i+1,r)+sum[r]-sum[l-1]);
	return dp[l][r];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	nn=n+n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];	
		a[i+n]=a[i];	
	}
	for(int i=1;i<=n;i++)
	{
		init(i,i+n);
		ans=min(dfs(i,i+n-1),ans);
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
	{
		init(i,i+n);
		ans=max(ddfs(i,i+n-1),ans);
	}
	cout<<ans<<endl;
	return 0;
}