算法1

区间dp

#include<bits/stdc++.h>
using namespace std;

int f[210][210],g[210][210],w[410],s[410];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i+n] = w[i];
    }
    for(int i=1;i<=n*2;i++)
        s[i] = s[i-1]+w[i];
    for(int len = 1;len<n;len++)
        for(int l=1;l+len<=n*2;l++)
        {
            int r = l+len;
            f[l][r] = INT_MAX;
            g[l][r] = INT_MIN;
            for(int k=l;k+1<=r;k++)
            {
                f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
                g[l][r] = max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
            }
        }
    int minn = INT_MAX,maxn = INT_MIN;
    for(int i=1;i<=n;i++)
    {
        minn = min(minn,f[i][i+n-1]);
        maxn = max(maxn,g[i][i+n-1]);
    }
    cout<<minn<<endl<<maxn;
}

算法2

记忆化搜索

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int f[410][410],g[410][410],w[410],s[410];
int minn = INT_MAX,maxn = INT_MIN;

int dp(int i,int j)
{
    if(i==j) return 0;
    int &v = f[i][j];
    if(v!=-1) return v;
    v = INT_MAX;
    for(int k=i;k+1<=j;k++)
        v = min(v,dp(i,k)+dp(k+1,j)+s[j]-s[i-1]);
    return v;
}

int dp2(int i,int j)
{
    if(i==j) return 0;
    int &v = g[i][j];
    if(v!=-1) return v;
    v = INT_MIN;
    for(int k=i;k+1<=j;k++)
        v = max(v,dp2(i,k)+dp2(k+1,j)+s[j]-s[i-1]);
    return v;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i+n] = w[i];
    }
    for(int i=1;i<=n*2;i++)
        s[i] = s[i-1]+w[i];
    memset(f,-1,sizeof f);
    memset(g,-1,sizeof g);
    for(int i=1;i<=n;i++)
    {
        minn = min(minn,dp(i,i+n-1));
        maxn = max(maxn,dp2(i,i+n-1));
    }
    cout<<minn<<endl<<maxn;
}