最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定 $n$ 个石子的 分数 $w_i$，且石子是 环形放置 的（在给定的顺序上，同时满足 $1$ 和 $n$ 也是相邻的）

规定每次只能合并 相邻 的两堆石子，形成一个新的石子堆，合并的 费用 是两个石子堆的 分数之和

求解两个方案：

1. 方案一：把这 $n$ 堆石子合并为一堆，且满足费用最大的方案
2. 方案二：把这 $n$ 堆石子合并为一堆，且满足费用最小的方案

分析

拓展：

如果每轮合并的石子 可以是任意 的 两堆 石子，那么用到的就是经典的 Huffman Tree 的二叉堆模型

如果每轮合并的石子 可以是任意 的 $n$ 堆 石子，那么用到的就是经典的 Huffman Tree 的 $n$ 叉堆模型

以上两种题型可以参考：

1. 二叉堆：AcWing 148. 合并果子
2. $n$ 叉堆：AcWing 149. 荷马史诗

回归本题，本题要求每轮合并的石子 必须是相邻的 两堆石子，因此不能采用 Huffman Tree 的模型

这类限制只能合并相邻两堆石子的模型，用到的是经典的 区间DP 模型

考虑如何设定 动态规划 的阶段，既可以表示出初始每个石子的费用，也可以表示出合并后整个堆的费用

不妨把当前合并的石子堆的大小作为DP的阶段

这样 $len=1$ 表示初值，即每个堆只有一个石子； $len=n$ 表示终值，即一个堆中有所有的石子

这种阶段设置方法保证了我们每次合并两个区间时，他们的所有子区间的合并费用都已经被计算出来了

阶段设定好后，考虑如何记录当前的状态，无外乎就两个参数：

1. 石子堆的左端点 $l$
2. 石子堆的右端点 $r$

闫氏DP分析法

状态表示—集合$f_{len,l,r}:$ 当前合并的石子堆的大小为 $len$，且石子堆的左端点是 $l$，右端点是 $r$ 的方案
状态表示—属性$f_{len,l,r}:$ 方案的费用最大/最小（本题两者都要求）
状态计算—$f_{len,l,r}:$

$$ \begin{cases} 计算最大值的转移：f_{len,l,r} = max(f_{k-l+1,l,k} + f_{len-(k-l+1),k+1,r} + cost_{l,r}) \quad (l \le k \lt r) \\\ 计算最小值的转移：f_{len,l,r} = min(f_{k-l+1,l,k} + f_{len-(k-l+1),k+1,r} + cost_{l,r}) \quad (l \le k \lt r) \end{cases} $$

初始状态： $f_{1,i,i} \quad (1\le i \le n)$
目标状态： $f_{n,1,n}$

在区间DP中，我们也常常省去 $len$ 这一维的空间

因为 $r-l+1 = len$，也就保证了在已知 $l$ 和 $r$ 的情况下，不会出现状态定义重复的情况

根据线性代数中方程的解的基本概念，我们就可以删掉 $len$ 这一维不存在的约束

但为了方便读者理解，以及介绍区间DP的阶段是如何划分的，我还是写了出来

以上就是所有有关石子合并的区间DP分析

在考虑一下本题的 环形相邻 情况如何解决，方案有如下两种：

1. 我们可以枚举环中分开的位置，将环还原成链，这样就需要枚举 $n$ 次，时间复杂度为 $O(n^4)$

2. 我们可以把链延长两倍，变成 $2n$ 个堆，其中 $i$ 和 $i+n$ 是相同的两个堆，然后直接套 区间DP 模板，但对于 阶段 $len$ 只枚举到 $n$，根据 状态的定义，最终可以得到所求的方案，时间复杂度为 $O(n^3)$

一般常用的都是第二种方法，我也只会演示第二种方法的写法，对第一种有兴趣的读者可以自行尝试

Code

时间复杂度：$O(n^3)$

#include <iostream>
#include <cstring>

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()
{
    //读入
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) cin >> w[i], w[i + n] = w[i];

    //预处理前缀和（DP状态转移中会频繁的用到区间和）
    for (int i = 1; i <= n << 1; ++ i) s[i] = s[i - 1] + w[i];

    memset(f, -0x3f, sizeof f);//求最大值预处理成最小值（可以省掉，这题不会有负数状态所以0就是最小）
    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;//预处理初始状态
            else
            {
                for (int k = l; k + 1 <= r; ++ k)//枚举分开点
                {
                    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);

    return 0;
}