深搜

#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;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, nn;
int a[405];
int sum[405];    // sum[i]: a[1]~a[i] 之和
int f[405][405]; // f[i][j] 表示 a[i]~a[j] 合并成一堆的最小消耗
int g[405][405]; // g[i][j] 表示 a[i]~a[j] 合并成一堆的最大消耗
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];
    }
    nn = n + n;
    // sum
    for (int i = 1; i <= nn; i++)
        sum[i] = sum[i - 1] + a[i];
    // f
    memset(f, 0x3f, sizeof(f));
    memset(g, -1, sizeof(g));
    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= nn; l++)
        {
            int r = l + len - 1;
            // 计算f[l][r]
            if (len == 1)
            {
                f[l][r] = 0;
                g[l][r] = 0;
                continue;
            }
            for (int k = l; k < r; k++) // 讨论区间划分点
            {
                // 当前的方案：
                // 先把 a[l]~a[k] 合并成一堆 : 最少消耗 f[l][k]
                // 再把 a[k+1]~a[r] 合并成一堆 : 最少消耗 f[k+1][r]
                // 最后把这两堆合并在一起
                f[l][r] = min(f[l][r],
                              f[l][k] + f[k + 1][r] + (sum[r] - sum[l - 1]));
                g[l][r] = max(g[l][r],
                              g[l][k] + g[k + 1][r] + (sum[r] - sum[l - 1]));
            }
        }
    int minn = 0x3f3f3f3f3f3f3f3fLL;
    int maxx = -1;
    for (int l = 1; l + n - 1 <= nn; l++)
    {
        minn = min(minn, f[l][l + n - 1]);
        maxx = max(maxx, g[l][l + n - 1]);
    }
    cout << minn << "\n"
         << maxx;
    return 0;
}