区间DP | 动态规划

参考《算法竞赛进阶指南》、AcWing题库

区间DP

到目前为止, 我们介绍的线性 DP一般从初态开始, 沿着阶段的扩张向某个方向递 推, 直至计算出目标状态。区间 DP 也属于线性 DP 中的一种, 它以 “区间长度” 作为 DP 的 “阶段”, 使用两个坐标 (区间的左、右端点) 描述每个维度。在区间 DP 中, 一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来, 因此区间 DP 的 决策往往就是划分区间的方法。区间 DP 的初态一般就由长度为 1 的 “元区间” 构成。 这种向下划分、再向上递推的模式与某些树形结构, 例如第 $0 \times 43$ 节的线段树, 有很大 的相似之处。我们把区间 DP 作为线性 DP 中一类重要的分支单独进行讲解, 将使读者 更容易理解下一节树形 DP 的内容。同时, 借助区间 DP 这种与树形相关的结构, 我们 也将提及记忆化搜索一其本质是动态规划的递归实现方法。

---

282. 石子合并

题目描述

设有 $N$ 堆石子排成一排，其编号为 $1，2，3，…，N$。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 $N$ 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 $4$ 堆石子分别为 1 3 5 2， 我们可以先合并 $1、2$ 堆，代价为 $4$，得到 4 5 2， 又合并 $1，2$ 堆，代价为 $9$，得到 9 2 ，再合并得到 $11$，总代价为 $4+9+11=24$；

如果第二步是先合并 $2，3$ 堆，则代价为 $7$，得到 4 7，最后一次合并代价为 $11$，总代价为 $4+7+11=22$。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 $N$ 表示石子的堆数 $N$。

第二行 $N$ 个数，表示每堆石子的质量(均不超过 $1000$)。

输出格式

输出一个整数，表示最小代价。

数据范围

$1 \le N \le 300$

输入样例：

4
1 3 5 2 

输出样例：

22 

算法分析

若最初的第 $l$ 堆石子和第 $r$ 堆石子被合并成一堆, 则说明 $l \sim r$ 之间的每堆石子 也已经被合并, 这样 $l$ 和 $r$ 才有可能相邻。因此, 在任意时刻, 任意一堆石子均可以用一个闭区间 $[l, r]$ 来描述, 表示这堆石子是由最初的第 $l \sim r$ 堆石子合并而成的, 其重量为 $\sum_{i=l}^{r} A_{i}$ 。另外, 一定存在一个整数 $k(l \leq k<r)$, 在这堆石子形成之前, 先 第 $l \sim k$ 堆石子 (闭区间 $[l, k])$ 被合并成一堆, 第 $k+1 \sim r$ 堆石子 (闭区间 $[k+1, r])$ 被合并成一堆, 然后这两堆石子才合并成 $[l, r]$ 。

对应到动态规划中, 就意味着两个长度较小的区间上的信息向一个更长的区间发 生了转移,划分点 $k$ 就是转移的决策。自然地, 应该把区间长度 $len$ 作为 DP 的阶段。不过, 区间长度可以由左端点和右端点表示出, 即 $l e n=r-l+1$ 。本着动态规划 “选择最小的能覆盖状态空间的维度集合” 的思想，可以只用左、右端点表示 DP 的状态。

设 $F[l, r]$ 表示把最初的第 $l$ 堆到第 $r$ 堆石子合并成一堆, 需要消耗的最少体力。 根据上述分析, 容易写出状态转移方程:

$$F[l, r]=\min _{l \leq k<r}\{F[l, k]+F[k+1, r]\}+\sum_{i=l}^{r} A_{i}$$

初值: $\forall l \in[1, N], F[l, l]=A_{l}$, 其余为正无穷。

目标: $F[1, N]$ 。

我们在分组背包最后强调, 编程实现动态规划的状态转移方程时, 务必分清阶段、状态与决策, 三者应该按照从外到内的顺序依次循环。对于 $\sum_{i=l}^{r} A_{i}$, 可使用前缀和计算。

Solution

#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int f[N][N];
int a[N],s[N];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  memset(f, 0x3f, sizeof f);//初始化INF
  for (int i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + a[i];//前缀和
    f[i][i] = 0;//合并一个石子不需要代价，len = 1 用来初始化
  }
  for (int len = 2; len <= n; ++len) {//以区间长度作为阶段，枚举从len = 2开始
    for (int l = 1; l + len - 1 <= n; ++l) {//状态左端点
      int r = l + len - 1;
      for (int k = l; k < r; ++k) {//决策
        f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
      }
      f[l][r] += s[r] - s[l - 1];
    }
  }
  cout << f[1][n];
}

---

1068. 环形石子合并

题目描述

将 $n$ 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 $n$ 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最小。

输入格式

第一行包含整数 $n$，表示共有 $n$ 堆石子。

第二行包含 $n$ 个整数，分别表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

数据范围

$1 \le n \le 200$

输入样例：

4
4 5 9 4 

输出样例：

43
54 

算法分析

拓展：

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

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

以上两种题型可以参考：

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

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

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

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

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

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

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

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

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

状态表示—集合$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+1$ 是相同的两个堆，然后直接套 区间DP 模板，但对于 阶段 $len$ 只枚举到 $n$，根据 状态的定义，最终可以得到所求的方案，时间复杂度为 $O(n^3)$

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

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

Solution

#include <iostream>
#include <cstring>
using namespace std;
const int N = 205;
int maxf[N * 2][N * 2];
int minf[N * 2][N * 2];
int a[N * 2], s[N * 2];
int main() {
  int n; 
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i], a[i + n] = a[i];
  
  memset(maxf, 0xc0, sizeof maxf);
  memset(minf, 0x3f, sizeof minf);
  for (int i = 1; i <= 2 * n; ++i) {
    maxf[i][i] = minf[i][i] = 0;
    s[i] = s[i - 1] + a[i];
  }
  
  for (int len = 2; len <= n; ++len) {
    for (int l = 1; r = l + len - 1, r <= 2 * n; ++l) {//r = 2 * n其实可以不用算，[1,n]中已经算过
      for (int k = l; k < r; ++k) {
        minf[l][r] = min(minf[l][r], minf[l][k] + minf[k + 1][r]);
        maxf[l][r] = max(maxf[l][r], maxf[l][k] + maxf[k + 1][r]);
      }
      minf[l][r] += s[r] - s[l - 1];
      maxf[l][r] += s[r] - s[l - 1];
    }
  }
  int minv = 0x3f3f3f3f, maxv = 0xc0c0c0c0;
  for (int l = 1; l + n - 1 <= 2 * n; ++l) {
    int r = l + n - 1;
    minv = min(minf[l][r], minv);
    maxv = max(maxf[l][r], maxv);
  }
  cout << minv << endl << maxv << endl;
}

---

320. 能量项链

题目描述

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 $N$ 颗能量珠。

能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。

并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m \times r \times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 $N=4$，$4$ 颗珠子的头标记与尾标记依次为 $(2，3) (3，5) (5，10) (10，2)$。

我们用记号 $⊕$ 表示两颗珠子的聚合操作，$(j⊕k)$ 表示第 $j$，$k$ 两颗珠子聚合后所释放的能量。则

第 $4、1$ 两颗珠子聚合后释放的能量为：$(4⊕1)=10 \times 2 \times 3=60$。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 $((4 \oplus 1) \oplus 2) \oplus 3) = 10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710$。

输入格式

输入的第一行是一个正整数 $N$，表示项链上珠子的个数。

第二行是 $N$ 个用空格隔开的正整数，所有的数均不超过 $1000$，第 $i$ 个数为第 $i$ 颗珠子的头标记，当 $i<N$ 时，第 $i$ 颗珠子的尾标记应该等于第 $i+1$ 颗珠子的头标记，第 $N$ 颗珠子的尾标记应该等于第 $1$ 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式

输出只有一行，是一个正整数 $E$，为一个最优聚合顺序所释放的总能量。

数据范围

$4 \le N \le 100$,
$1 \le E \le 2.1 \times 10^9$

输入样例：

4
2 3 5 10 

输出样例：

710 

算法分析

给定 $N$ 个能量石，每个能量石有一个二元属性 $(w_{i,1}, w_{i,2})$

其中 $w_{i,1}$ 表示第 $i$ 个能量石和第 $i-1$ 个能量石融合产生的 能量 的其中一个参数

当然 $w_{i,2}$ 表示第 $i$ 个能量石和第 $i+1$ 个能量石融合产生的 能量 的其中一个参数

魔法石是顺序且环形摆放的，每次可以融合相邻两个魔法石

融合两个能量石 $i,i+1$ 所产生的能量为（题目保证，相邻能量石的参数一致，首尾一致）

$$E_{i,i+1} = w_{i,1} \times (w_{i,2} 或 w_{i+1,1}) \times w_{i+1,1}$$

融合后左侧魔法石的第一个参数和右侧魔法石的第二个参数合并成为一颗新的 魔法石

具体如下图所示：

求最终把所有石头融合成一个石头时，产生的最大能量值

本题可以把区间长度作为搜索的阶段来进行记忆话搜索，因此我们也可以采用 区间DP 的方式来处理

这题和 环形石子合并 十分相似，但又不尽相同

在 环形石子 中，每个石头只有单一的参数，而本题有两个参数，也就意味着我们需要在细节上做出改变

经过观察我们发现，合并两个石头 $(a,b),(b,c)$ 的操作就像是矩阵乘法一样，合并完后就变成了 $(a,c)$

因此我们可以离散的来存储每个参数，具体如下所示：

这样 状态表示 就更新为：当前合并的石子堆的左端石头的左参数是 $l$，右端石头的右参数是 $r$ 的方案

这样对应的 初始状态 本来应该是一个有着 二元属性 的石头，现在就变成了长度为 $2$ 的区间

这样合并区间后，需要记录的新石头的参数也刚好是 区间的两端 对应的参数，如下图所示：

而且这里我们的转移方程也要修改为 $f_{l,r} = max(f_{l,k} + f_{k,r} + E_{l,r})$

以往的 区间DP 我们是把区间 $[a,b]$ 拆分为 $[a,k] 和 [k+1,b]$

因为 同一个石子 只会被合并到 一个石子堆 里

但本题合并魔法石时，分割点 $k$ 要被分到 左侧石子堆的右端点 和 右侧石子堆的左端点 中

因此，参数 $k$ 要作为两个区间的共同端点来使用，即 $[a,k]$ 和 $[k,b]$

此外我们原来只需要合并 $n$ 个石头，这样转换后就要合并 $n+1$ 个石头了

状态表示—集合$f_{l,r}:$ 当前合并的石子堆的左端石头的左参数是 $l$，右端石头的右参数是 $r$ 的方案

状态表示—属性$f_{l,r}:$ 方案的费用最大

状态计算—$f_{l,r}:$

$$f_{l,r} = max(f_{l,k} + f_{k,r} + E_{l,r}) \quad (l \lt k \lt r)$$

初始状态： $f_{l,l+1} = 0 \quad(1\le l \le n)$

目标状态： $f_{1,n + 1}$

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

Solution

预处理每个能量珠，整合成一个物体

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

const int N = 105;
int f[2 * N][2 * N];
int a[2 * N];
pair<int,int> w[2 * N];

int main() {
  int n; 
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i], a[i + n] = a[i];
  for (int i = 1; i + 1 <= 2 * n; ++i) w[i].first = a[i], w[i].second = a[i + 1];
  w[2 * n].first = a[2 * n], w[2 * n].second = a[1];
  
  for (int len = 2; len <= n; ++len) {
    for (int l = 1, r; r = l + len - 1, r <= 2 * n; ++l) {
      if (l == r) {
        f[l][r] = 0;
        continue;
      }
      for (int k = l; k < r; ++k) {
        f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + w[l].first * w[k].second * w[r].second);
      }
    }
  }
  
  int maxv = 0xc0c0c0c0;
  for (int l = 1; l + n - 1 <= 2 * n; ++l) maxv = max(f[l][l + n - 1], maxv);
  cout << maxv;
} 

直接计算，要注意2个数对应一个能量珠

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

const int N = 105;
int f[2 * N][2 * N];
int a[2 * N];

int main() {
  int n; 
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i], a[i + n] = a[i];

  for (int len = 3; len <= n + 1; ++len) {
    for (int l = 1, r; r = l + len - 1, r <= 2 * n; ++l) {
      for (int k = l + 1; k < r; ++k) {
        f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
      }
    }
  }
  
  int maxv = 0xc0c0c0c0;
  for (int l = 1, r; r = l + (n + 1) - 1, r <= 2 * n; ++l) maxv = max(f[l][r], maxv);
  cout << maxv;
} 

---

479. 加分二叉树

题目描述

设一个 $n$ 个节点的二叉树 tree 的中序遍历为（$1,2,3,…,n$），其中数字 $1,2,3,…,n$ 为节点编号。

每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：

subtree的左子树的加分 $×$ subtree的右子树的加分 $＋$ subtree的根的分数

若某个子树为空，规定其加分为 $1$。

叶子的加分就是叶节点本身的分数，不考虑它的空子树。

试求一棵符合中序遍历为（$1,2,3,…,n$）且加分最高的二叉树 tree。

要求输出：

（1）tree的最高加分

（2）tree的前序遍历

输入格式

第 $1$ 行：一个整数 $n$，为节点个数。

第 $2$ 行：$n$ 个用空格隔开的整数，为每个节点的分数（$0<$分数$<100$）。

输出格式

第 $1$ 行：一个整数，为最高加分（结果不会超过int范围）。

第 $2$ 行：$n$ 个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围

$n < 30$

输入样例：

5
5 7 1 2 10 

输出样例：

145
3 1 2 4 5 

算法分析

给定一个含有 $n$ 个结点的二叉树的 中序遍历 序列中每个节点的 权值

定义一棵 子树 的 分数 为 $左子树的分数 \times 右子树的分数 + 根节点的权值$

额外规定 空树 的 分数 为 $1$

求一种满足该 中序遍历 的建树方案，使得整棵树的 分数 最大

因为本题是一道与树相关的区间DP，因此本题解采用 记忆化搜索 的思想来分析，抛开常规 动态规划 思路

首先读者需要知道一个二叉树的小常识：

二叉树节点 向下投影，映射成的数组序列就是 中序遍历序列，入下图所示

这也是诱使我们本题采用 区间DP 的一大原因之一（但这篇题解采用 记忆化搜索 思想分析）

借助上图直观的表象，我们发现可以任意的选择 中序遍历 的某一段区间便可生成多棵子树（枚举根节点）

于是我们就会想到 分治 的思想，枚举好根节点后，递归的处理左右区间生成的 最大分数子树

回溯后，利用计算好的子树的分数 相乘，再加上根结点的 权值，就可以得出该方案的 最大分数

而直接递归 搜索 的时间复杂度是 $O(n!)$（每次枚举当前区间的根结点，然后递归处理左右区间）

$n \times (n-1) \times \cdots \times 1 = n!$ （每次向下层递归时，会确定一个根节点，因此每次少 $1$）

---

因为在这个递归中，有相当大的计算是去处理的 相同的区间

因此我们不妨采用 记忆化搜索 的形式优化掉这些 重复的搜索

考虑用数组 $f_{l,r}$ 记录以 $l$ 为左端点，$r$ 为右端点的区间，生成的树的最大分数

这样就会 剪枝 掉相当大的冗余 搜索分支

状态表示—集合$f_{l,r}:$ 当前以 $l$ 为左端点，$r$ 为右端点的区间作为 中序遍历，生成树的方案

状态表示—属性$f_{l,r}:$ 方案的分数最大

状态计算—$f_{l,r}:$

$$f_{l,r} = max(f_{l,k - 1} \times f_{k + 1, r} + w_k) \quad (l \le k \lt r)$$

初始状态： $f_{l,l} = w_l$ 题设规定只有一个节点的子树分数就是其权值

目标状态： $f_{l,r}$

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

Solution

循环

#include <iostream>
using namespace std;
const int N = 35;

int f[N][N];
int a[N];
int root[N][N];

void dfs(int l, int r) {
  if (l > r) return;
  
  int k = root[l][r];
  cout << k << " ";
  
  dfs(l, k - 1);
  dfs(k + 1, r);
}

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  for (int len = 1; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
      int r = l + len - 1;
      if (len == 1) {
        f[l][r] = a[l];
        root[l][r] = l;
        continue;
      }
      for (int k = l; k <= r; ++k) {
        int left = k == l ? 1 : f[l][k - 1];
        int right = k == r ? 1 : f[k + 1][r];
        int score = left * right + a[k];
        if (f[l][r] < score) {
          f[l][r] = score;
          root[l][r] = k;
        }
      }
    }
  }
  
  cout << f[1][n] << endl;
  dfs(1, n);
}

记忆化搜索

#include <iostream>
#include <cstring>
using namespace std;
const int N = 35;

int f[N][N];
int a[N];
int root[N][N];

int dp(int l, int r) {
  if (f[l][r] != -1) return f[l][r];
  if (l == r) return root[l][r] = l, f[l][r] = a[l];//逗号表达式值为最后一个表达式的值
  if (l > r) return f[l][r] = 1;
  
  int maxv = 0;
  for (int k = l; k <= r; ++k) {
    int score = dp(l, k - 1) * dp(k + 1, r) + a[k];
    if (score > maxv) {
      maxv = score;
      root[l][r] = k;
    }
  }
  return f[l][r] = maxv;
}

void dfs(int l, int r) {
  if (l > r) return;
  
  int k = root[l][r];
  cout << k << " ";
  
  dfs(l, k - 1);
  dfs(k + 1, r);
}

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  memset(f, -1, sizeof f);
  cout << dp(1, n) << endl;
  
  dfs(1, n);
}

---

1069. 凸多边形的划分

题目描述

给定一个具有 $N$ 个顶点的凸多边形，将顶点从 $1$ 至 $N$ 标号，每个顶点的权值都是一个正整数。

将这个凸多边形划分成 $N-2$ 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

输入格式

第一行包含整数 $N$，表示顶点数量。

第二行包含 $N$ 个整数，依次为顶点 $1$ 至顶点 $N$ 的权值。

输出格式

输出仅一行，为所有三角形的顶点权值乘积之和的最小值。

数据范围

$N \le 50$,
数据保证所有顶点的权值都小于$10^9$

输入样例：

5
121 122 123 245 231 

输出样例：

12214884 

算法分析

这是一个经典的 图形学 问题 — 三角剖分

因为我们现实中常见的一些 多边形图形 存储到计算机中，需要转存为一个个 像素点

那么如何存储一个 多边形 最简单的方案就是把它转化为 多个三角形 进行存储

也就是 三角剖分 问题，不只是 凸多边形，还能解决 凹多边形， 有孔多边形 等问题

对应有 $O(n^3)$ 的暴力算法，$O(n^2)$ 的 $ear clipping$ 算法，$O(n\log n)$ 的 $Delaunay$ 算法

还有很复杂的线性算法

---

以上和本题都没啥关系，大家有兴趣学习的可以自行翻阅文献和资料

回归本题，本题是一个给定的 凸多边形 求 三角剖分 的最小费用方案

很显然一个 凸多边形的剖分方案 并不唯一：

在 选定 多边形中 两个点 后，找出 三角形 的 第三个点 的方案有 $n-2$ 个

然后还要分别 划分 他的 左右两块区域

因此我们就会想到用 记忆化搜索 或者 区间DP 来进行处理

状态表示—集合$f_{l,r}:$ 当前划分到的多边形的左端点是 $l$，右端点是 $r$ 的方案

状态表示—属性$f_{l,r}:$ 方案的费用最小

状态计算—$f_{l,r}:$

$$f_{l,r} = min(f_{l,k} + f_{k,r} + w_l \times w_k \times w_r) \quad (l \lt k \lt r)$$

区间DP 在状态计算的时候一定要 认真 划分好 边界 和 转移，对于不同题目是不一样的

然后本题非常的嚣张，直接用样例的 $5$ 的点告诉我们答案会爆 $int$ 和 $long \; long$

并且没有 取模 要求，那就只能上 高精度 了 ~用Python了~

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

Solution

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

const int N = 55;

vector<int> f[N][N];
int w[N];

bool cmple(const vector<int> &a, const vector<int> &b) {
  if (a.size() != b.size()) return a.size() < b.size();
  for (int i = a.size() - 1; i >= 0; --i) {
    if (a[i] != b[i]) return a[i] < b[i];
  }
  return true;
}

vector<int> add(const vector<int> &a, const vector<int> &b) {
  vector<int> c;
  int t = 0;
  for (int i = 0; i < a.size() || i < b.size(); ++i) {
    if (i < a.size()) t += a[i];
    if (i < b.size()) t += b[i];
    c.push_back(t % 10);
    t /= 10;
  }
  while (t) c.push_back(t % 10), t /= 10;
  return c;
}

vector<int> mul(const vector<int> &a, long long b) {
  vector<int> c;
  long long t = 0;
  for (int i = 0; i < a.size(); ++i) {
    t += a[i] * b;
    c.push_back(t % 10);
    t /= 10;
  }
  while (t) {
    c.push_back(t % 10);
    t /= 10;
  }
  return c;
}


int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> w[i];
  
  for (int len = 3; len <= n; ++len) {
    for (int l = 1, r;  (r = l + len - 1) <= n; ++l) {
      for (int k = l + 1; k < r; ++k) {
        auto newval = mul(mul({w[l]}, w[k]), w[r]);
        newval = add(add(newval, f[l][k]), f[k][r]);
        if (f[l][r].empty() || cmple(newval, f[l][r])) {
          f[l][r] = newval;
        }
      }
    }
  }
  
  auto &ans = f[1][n];
  for (int i = ans.size() - 1; i >= 0; --i) cout << ans[i];
  
}

---

321. 棋盘分割

题目描述

将一个 $8 \times 8$ 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了 $(n-1)$ 次后，连同最后剩下的矩形棋盘共有 $n$ 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。

现在需要把棋盘按上述规则分割成 $n$ 块矩形棋盘，并使各矩形棋盘总分的均方差最小。

均方差，其中平均值，$x_i$ 为第 $i$ 块矩形棋盘的总分。

请编程对给出的棋盘及 $n$，求出均方差的最小值。

输入格式

第 $1$ 行为一个整数 $n$。

第 $2$ 行至第 $9$ 行每行为 $8$ 个小于 $100$ 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出格式

输出最小均方差值（四舍五入精确到小数点后三位）。

数据范围

$1 < n < 15$

输入样例：

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3 

输出样例：

1.633 

算法分析

这个题目很重要的条件就是：

每次切割都只能沿着棋盘格子的边进行。

关于这个条件的解释，题面中已经写的很清楚了，我就不赘述了。

考虑使均方差 $\sigma=\sqrt{\dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}{n}}$ 最小

则考虑使标准差 $\alpha=\dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}{n}$ 最小

分析得到 $\bar{x}=\dfrac{\sum\limits_{i=1}^nx_i}{n}$ 无论 $x_i$ 的取值 ，$\bar{x}$ 恒等于 $\dfrac{\sum\limits_{i=1}^8\sum\limits_{j=1}^8w_{i,j}}{n}$，其中 $w_{i,j}$ 代表每一个格子上的数。

所以可以预处理 $\bar{x}$。

此时可以发现将每个 $x_i$ 分开考虑，使得 $\dfrac{(x_i-\bar{x})^2}{n}$ 最小，即考虑使用动态规划。

由于此题是一个比较明显的区间分割问题，考虑使用区间 DP。

令 $f_{x_1,y_1,x_2,y_2,k}$ 表示将子矩阵 $(x_1,y_1)(x_2,y_2)$ 划分为 $k$ 个子矩阵的最小标准差 $\alpha$，则最终答案为 $\sqrt{f_{1,1,8,8,n}}$。

边界 $k=1$ 时，$f_{x_1,y_1,x_2,y_2,k}=\dfrac{((\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}w_{i,j})-\bar{x})^2}{n}$

在状态转移时，分类讨论水平切还是竖直切，枚举在哪里切，再分类讨论是要哪一块。

则可得出状态转移方程（详见代码）。

注意可用二维前缀和来维护子矩阵，从而 $O(1)$ 得到子矩阵的和。

总时间复杂度 $O(8^5n)$。

由于循环太多，采用记忆化搜索写。

代码中 X 即为 $\bar{x}$，get 函数是求 $\dfrac{(x_i-\bar{x})^2}{n}$，s 即为二位前缀和数组。

再次强调 $f_{x_1,y_1,x_2,y_2,k}$ 是存储的将子矩阵 $(x_1,y_1)(x_2,y_2)$ 划分为 $k$ 个子矩阵的最小标准差 $\alpha$，所以最后还要开根号！

Solution

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

const int N = 10, M = 20;

int n;
double f[N][N][N][N][M];
double s[N][N];
double X;

double get(int x1, int y1, int x2, int y2) {
  double sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
  return (sum - X) * (sum - X) / n;
}

double dp(int x1, int y1, int x2, int y2, int k) {
  double &v = f[x1][y1][x2][y2][k];
  if (v >= 0) return v;
  if (k == 1) return v = get(x1, y1, x2, y2);
  
  v = 1e9;
  for (int i = x1; i < x2; ++i) {
    v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));
    v = min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
  }
  
  for (int j = y1; j < y2; ++j) {
    v = min(v, dp(x1, y1, x2, j, k - 1) + get(x1, j + 1, x2, y2));
    v = min(v, dp(x1, j + 1, x2, y2, k - 1) + get(x1, y1, x2, j));
  }
  
  return v;
}

int main() {
  cin >> n;
  for (int i = 1; i <= 8; ++i) {
    for (int j = 1; j <= 8; ++j) {
      cin >> s[i][j];
      s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
  }

  X = s[8][8] / n;
  
  memset(f, -1, sizeof f);
  cout << fixed << setprecision(3) << sqrt(dp(1, 1, 8, 8, n));
}

---

283. 多边形

题目描述

“多边形游戏”是一款单人益智游戏。

游戏开始时，给定玩家一个具有 $N$ 个顶点 $N$ 条边（编号 $1 \sim N$）的多边形，如图 $1$ 所示，其中 $N = 4$。

每个顶点上写有一个整数，每个边上标有一个运算符 +（加号）或运算符 *（乘号）。

第一步，玩家选择一条边，将它删除。

接下来在进行 $N-1$ 步，在每一步中，玩家选择一条边，把这条边以及该边连接的两个顶点用一个新的顶点代替，新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到的结果。

下面是用图 $1$ 给出的四边形进行游戏的全过程。

最终，游戏仅剩一个顶点，顶点上的数值就是玩家的得分，上图玩家得分为 $0$。

请计算对于给定的 $N$ 边形，玩家最高能获得多少分，以及第一步有哪些策略可以使玩家获得最高得分。

输入格式

输入包含两行，第一行为整数 $N$。

第二行用来描述多边形所有边上的符号以及所有顶点上的整数，从编号为 $1$ 的边开始，边、点、边…按顺序描述。

其中描述顶点即为输入顶点上的整数，描述边即为输入边上的符号，其中加号用 t 表示，乘号用 x 表示。

输出格式

输出包含两行，第一行输出最高分数。

在第二行，将满足得到最高分数的情况下，所有的可以在第一步删除的边的编号从小到大输出，数据之间用空格隔开。

数据范围

$3 \le N \le 50$,
数据保证无论玩家如何操作，顶点上的数值均在 $[-32768,32767]$ 之内。

输入样例：

4
t -7 t 4 x 2 x 5 

输出样例：

33
1 2 

算法分析

Solution

---

284. 金字塔

题目描述

虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。

经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。

首先，金字塔由若干房间组成，房间之间连有通道。

如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。

并且，每个房间的墙壁都涂有若干种颜色的一种。

探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。

这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。

机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。

最后，机器人会从入口退出金字塔。

显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。

但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。

现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。

因为结果可能会非常大，你只需要输出答案对$10^9$ 取模之后的值。

输入格式

输入仅一行，包含一个字符串 $S$，长度不超过 $300$，表示机器人得到的颜色序列。

输出格式

输出一个整数表示答案。

输入样例：

ABABABA 

输出样例：

5 

算法分析

Solution

---