算法提高之环形石子合并

• 核心思想：区间dp

  • 状态表示：f[len,l,r]表示长度为len的堆 左端点l右端点r
  • 状态计算：在l~r找一点k 分成两段

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 210,M = N<<1,INF = 0x3f3f3f3f;
    
    int n;
    int w[M],s[M];
    int f[M][M],g[M][M];
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>w[i],w[i+n] = w[i];  //石子开成两倍
        
        for(int i=1;i<=n<<1;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 l=1,r;r=l+len-1,r<n<<1;l++)  //遍历左端点
            {
                if(len == 1) f[l][l] = g[l][l] = 0;  //只有一个l点 数值为0
                else
                {
                    for(int k=l;k+1<=r;k++)  //l~r中某点
                    {
                        f[l][r] = max(f[l][r],f[l][k] + f[k+1][r] + s[r] - s[l-1]);
                        g[l][r] = min(g[l][r],g[l][k] + g[k+1][r] + s[r] - s[l-1]);
                    }
                }
            }
        }
        int minv = INF, maxv = -INF;
        for (int l = 1; l <= n; ++ l)
        {
            minv = min(minv, g[l][l + n - 1]);
            maxv = max(maxv, f[l][l + n - 1]);
        }
    
        printf("%d\n%d\n", minv, maxv);
    }