区间dp

把环变成链子来写

//1068 环形区间dp 写法:迭代式 或者记忆化搜索

#include <iostream>//时间复杂度 （2n）的3次方
#include <cstring>
#include <algorithm>//石子合并变成环形
using namespace std;
const int N = 410,INF=0x3f3f3f3f;//把链拉长
int n;
int w[N];
int s[N];
int f[N][N];//MIN
int g[N][N];//存的是合并的MAX
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int c;
        cin>>c;
        w[i]=w[i+n]=c;
    }
    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 l=i,r=i+len-1;
        if(len==1)  f[l][r]=g[l][r]=0;//不需要一点能量
       // f[l][r]=INF;
        //g[l][r]=-INF;
        for(int k=l;k<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 maxd=-INF,mind=INF;
    for(int i=1;i+n-1<=2*n;i++)//然后枚举每个区间 找到最大最下值
    {
        maxd=max(maxd,g[i][i+n-1]);
        mind=min(mind,f[i][i+n-1]);
    }
    cout<<mind<<endl<<maxd<<endl;
    return 0;
}