注意要把环形的展开成2*n长度的链！然后遍历每个i到i+n-1的区间

区间dp步骤

1. 枚举长度从1~n(环形的为1~2n)
2. 枚举起点i，1~n-len+1 (其中n为总长，若环形则为2n，下同)
3. 记录终点j=i+len-1
4. 枚举分界线[k,j)

#include <iostream>
#include <cstring>
using namespace std;

const int N=410;

int s[2*N],w[2*N];
int f[N][N],g[N][N];

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<=2*n;i++)
    {
        s[i]=s[i-1]+w[i];
    }

    memset(f,0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);

    for(int len=1;len<=2*n;len++)
    {
        for(int i=1;i+len-1<=2*n;i++)
        {
            int j=i+len-1;
            if(len==1) f[i][j]=g[i][j]=0;
            else
            {
                for(int k=i;k<j;k++)
                {
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                    g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
                }

            }
        }
    }

    int res1,res2;
    res1=0x3f3f3f3f;
    res2=-res1;

    for(int i=1;i<=n;i++)
    {
        res1=min(res1,f[i][i+n-1]);
        res2=max(res2,g[i][i+n-1]);
    }
    cout<<res1<<endl<<res2;

    return 0;
}

二刷，注意

1. i:[1,2*n-len+1]注意+1
2. j=i+len-1 如果i=1,len=1 那么j=i。因为len是区间长度，不是i和j 之间的距离

#include <iostream>
#include <cstring>

using namespace std;

const int N=210;
int f[N][N],g[N][N],s[2*N],w[2*N];


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<=2*n;i++) s[i]=s[i-1]+w[i];

    memset(f,0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);

    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=2*n;i++)
        {
            int j=i+len-1;
            if(len==1) g[i][j]=f[i][j]=0;
            else
            {
                for(int k=i;k<j;k++)
                {
                    g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                }

            }
        }
    }

    int min_res=0x3f3f3f3f;
    int max_res=-min_res;
    for(int i=1;i<=n;i++)
    {
        min_res=min(min_res,f[i][i+n-1]);
        max_res=max(max_res,g[i][i+n-1]);
    }
    cout<<min_res<<endl<<max_res;
    return 0;
}