- 1、 石子合并
- 2、环形石子合并（环形区间转换成一维）
- 3、能量项链（环形区间转换成一维）
- 4、凸多边形的划分（区间DP+高精度）
- 5、加分二叉树（区间DP记录方案数）
- 6、棋盘分割（二维区间DP、记忆化搜索实现（循环太长不方便））
区间DP问题的代码一般有两种：
- 迭代式：适用于一维区间DP
- 记忆化搜索：适用于二维区间DP
ACWing 282
集合
f[i, j]：所有将从i到j这段石子合并成一堆石子的合并方式的价值最大值
集合划分
以最后一次合并的分界线来分类，因为最后一次一定是两个集合合并。假设总共有 k = j - i + 1个元素，则划分方案为：
- 左边1个，右边k-1个；
- 左边2个，右边k-2个；
- …
- 左边k-1个，右边1个；
状态计算
假设在最后一步划分情况为[i,k], [k+1, j]，那么在计算最终最小代价之前的一步的最小代价为f[i,k]+f[k+1,j]，最终的最小代价就是加上区间[i,j]的和（最后一步的代价是固定的）。总的代价为
f[i,j] = min(f[i,k]+f[k+1,j]+s[j]-s[i-1])（s[i]表示区间1~i的前缀和），其中k∈[i, j-1]（右边至少要有一堆，不能枚举到k=j）。
#include2、环形石子合并（环形区间转换成一维）#include using namespace std; const int N = 310; int n; int s[N]; // 前缀和 int f[N][N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]); // 处理前缀和 for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1]; // 前两个for循环是在枚举所有子区间 for (int len = 2; len <= n; len ++ ) // 从小到大枚举状态：区间长度。当长度为1时，合并不需要代价，故从2开始 for (int i = 1; i + len - 1 <= n; i ++ ) // 枚举起点 { int l = i, r = i + len - 1; f[l][r] = 1e9; for (int k = l; k < r; k ++ ) // 枚举分界点，k不能取到r，因为右边至少要有一堆 f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); } printf("%dn", f[1][n]); return 0; }
ACwing 1068
将环拆成链的做法是将原来长度为n的环在任一点断开，将其长度扩展成2n后，就能在一条长度为2n的一维链上找到所有环里面长度为n的链。
#include3、能量项链（环形区间转换成一维）#include #include using namespace std; const int N = 410, INF = 0x3f3f3f3f; int n; int s[N], w[N]; int f[N][N], g[N][N]; // 一个最小值DP，一个最大值DP 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 * 2; 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; l + len - 1 <= n * 2; l ++ ) { int r = l + len - 1; if (len == 1) f[l][r] = g[l][r] = 0; // 仅有一个值的时候 else { 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 minv = INF, maxv = -INF; for (int i = 1; i <= n; i ++ ) { minv = min(minv, f[i][i + n - 1]); maxv = max(maxv, g[i][i + n - 1]); } cout << minv << endl << maxv << endl; return 0; }
ACwing 320
先考虑链式，最后环形根据上题经验计算。
本题输入的矩阵是(2，3)(3，5)(5，10)(10，2)，现将其处理成2, 3, 5, 10, 2，也就是(2, 3)、(3, 5)...的简化表示。
集合
f[L,R]：所有将[L,R]合并为一个矩阵（珠子）的方式的价值的最大值
集合划分
按划分的分界线来划分：
状态计算
若划分的分界线为K，所以第K个能量f[L, K] + f[K,R] + W[L]*W[K]*W[R]，故总的f[L,R] = max(f[L, K] + f[K,R] + W[L]*W[K]*W[R])
环形只需要枚举2n上的所有n + 1个长度的区间中的最大值即可（环形的处理跟上一题思路一样）。
#include4、凸多边形的划分（区间DP+高精度）#include using namespace std; const int N = 210; int n; int w[N]; int f[N][N]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> w[i]; w[i + n] = w[i]; } for (int len = 3; len <= n + 1; len++) // 注意这里的长度，要合并最小长度是3；从1开始转一圈会回到1，所以是n+1 for (int l = 1; l + len - 1 <= n * 2; l++) { int r = l + len - 1; for (int k = l + 1; k < r; k++) f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]); } int res = 0; for (int i = 1; i <= n; i++) // 枚举所有长度是n+1的区间 res = max(res, f[i][i + n]); cout << res << endl; return 0; }
ACwing 1069
考虑一种随机情况，当多边形被划分成如下情况时候，又因为题目中有“N−2三角形个互不相交”的前提条件，所以这三个部分相互独立，故这个时候的权值之和就可以表示成：左边的权值+右边的权值+这个三角形的权值，整个的最小值就是三个部分的最小值求和。
这里的状态表示成：f[1, 6] = f[1, 4] + f[4, 6] + w[1] * w[4] * w[6]
集合
f[L, R]：所有将(L，L+1)，(L+1，L+2)，...，(R-1， R)，(R，L)这个多边形划分成若干个三角形的方案数的价值的最小值
集合划分
根据(L，R)这条边属于那个三角形来划分，将多边形划分成三个部分
状态计算
f[L, R] = f[L, K] + f[K, R] + w[L] * w[K] * w[R] （与上一个题的状态转移方程一模一样）
未使用高精度的代码：
#include#include using namespace std; const int N = 55, INF = 1e9; int n; int w[N]; int f[N][N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> w[i]; for (int len = 3; len <= n; len++) for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; f[l][r] = INF; for (int k = l + 1; k < r; k++) // k只能循环到r-1，才能构成三角形 f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]); } cout << f[1][n] << endl; return 0; }
使用高精度的代码：
#include5、加分二叉树（区间DP记录方案数）#include using namespace std; typedef long long LL; const int N = 55; int n; int w[N]; vector f[N][N]; // 比较大小 bool cmp(vector &a, vector &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 add(vector a, vector b) { vector 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 mul(vector a, LL b) { vector c; LL t = 0; for (int i = 0; i < a.size(); i ++ ) { t += b * a[i]; c.push_back(t % 10); t /= 10; } while (t) c.push_back(t % 10), t /= 10; return c; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &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 new_val = mul(mul({w[l]}, w[k]), w[r]); new_val = add(add(new_val, f[l][k]), f[k][r]); if (f[l][r].empty() || cmp(new_val, f[l][r])) f[l][r] = new_val; } auto res = f[1][n]; for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]); printf("n"); return 0; }
ACwing 479
由题：每棵子树的中序遍历序列都是连续的。
集合
f[L,R]：所有中序遍历是[L,R]这一段的二叉树的集合的分值最大值
集合划分
按根结点的位置来划分
状态计算
假设根结点的位置在第k个点，左子树[L,k-1]，右子树[k+1,R]，且左右子树是独立的。所以总的最大值即为左边最大值 + 右边最大值 + w[k]，即为f[L, k-1] + f[k+1, R] + w[k]。
#include6、棋盘分割（二维区间DP、记忆化搜索实现（循环太长不方便））#include using namespace std; const int N = 30; int n; int w[N]; int f[N][N], g[N][N]; //g(l, r)用于记录(l, r)区间内的根结点 // 输出方案 void dfs(int l, int r) { if (l > r) return; int root = g[l][r]; cout << root << ' '; dfs(l, root - 1); dfs(root + 1, r); } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> w[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] = w[l]; g[l][r] = l; // 根结点是自己 } else { for (int k = l; k <= r; k++) { int left = k == l ? 1 : f[l][k - 1]; // k == l 表示左子树为空 int right = k == r ? 1 : f[k + 1][r]; // k == r 表示右子树为空 int score = left * right + w[k]; if (f[l][r] < score) // 是为了找到字典序最小的方案，找尽可能左边的，也就是说如果在k取不同的值但是score相同，我们优先取得最左边（第一个出现的）k { f[l][r] = score; g[l][r] = k; } } } } cout << f[1][n] << endl; dfs(1, n); return 0; }
ACwing 321
由题，要使均方差 ∑ i = 1 n ( x i − x ˉ ) 2 n sqrt{frac{sum_{i=1}^{n}(x_i-bar{x})^2}{n}} n∑i=1n(xi−xˉ)2 最小，只需要使 ∑ i = 1 n ( x i − x ˉ ) 2 n frac{sum_{i=1}^{n}(x_i-bar{x})^2}{n} n∑i=1n(xi−xˉ)2 最小即可，又因为有： ∑ i = 1 n ( x i − x ˉ ) 2 n = ∑ i = 1 n x i 2 n − x ˉ 2 frac{sum_{i=1}^{n}(x_i-bar{x})^2}{n}=frac{sum_{i=1}^nx_i^2}{n}-bar{x}^2 n∑i=1n(xi−xˉ)2=n∑i=1nxi2−xˉ2，且 x ˉ 2 bar{x}^2 xˉ2 固定，所以我们只需求 ∑ i = 1 n x i 2 sum_{i=1}^nx_i^2 ∑i=1nxi2 ，即每一部分的平方和的最小值即可。
化简过程： ∑ i = 1 n ( x i − x ˉ ) 2 n = 1 n ( ∑ i = 1 n ( x i 2 − 2 x i x ˉ + x ˉ 2 ) ) = 1 n ( ∑ i = 1 n x i 2 − x ˉ ∑ i = 1 n 2 x i + n x ˉ 2 ) = 1 n ( ∑ i = 1 n x i 2 − x ˉ 2 n x ˉ + n x ˉ 2 ) = 1 n ( ∑ i = 1 n x i 2 − n x ˉ 2 ) = ∑ i = 1 n x i 2 n − x ˉ 2 frac{sum_{i=1}^{n}(x_i-bar{x})^2}{n} = frac{1}{n}(sum_{i=1}^{n}(x_i^2-2x_ibar{x}+bar{x}^2))=frac{1}{n}(sum_{i=1}^nx_i^2-bar{x}sum_{i=1}^n2x_i+nbar{x}^2)=frac{1}{n}(sum_{i=1}^nx_i^2-bar{x}2nbar{x}+nbar{x}^2)=frac{1}{n}(sum_{i=1}^nx_i^2-nbar{x}^2)=frac{sum_{i=1}^nx_i^2}{n}-bar{x}^2 n∑i=1n(xi−xˉ)2=n1(i=1∑n(xi2−2xixˉ+xˉ2))=n1(i=1∑nxi2−xˉi=1∑n2xi+nxˉ2)=n1(i=1∑nxi2−xˉ2nxˉ+nxˉ2)=n1(i=1∑nxi2−nxˉ2)=n∑i=1nxi2−xˉ2
上面化简过程偶尔会用到，注意推导。下面是不化简解决问题的过程。
集合
f[x1, y1, x2, ye, k]：子矩阵(x1,y1)(x2,y2)切分成k部分的所有方案中 ∑ i = 1 n ( x i − x ˉ ) 2 n frac{sum_{i=1}^{n}(x_i-bar{x})^2}{n} n∑i=1n(xi−xˉ)2 的最小值，其中(x1,y1)是矩阵左上角，(x2,y2)是矩阵右下角坐标。
集合划分
对于一个mxn的矩阵
- 按最后一次切的方向来划分，分成横切和纵切
- 在每种切法里面，可以分别切横向m刀和纵向n刀
- 在每一刀里面，还可以进一步划分
- 对于横切，分为取上半部分和下半部分
- 对于纵切，分为取左半部分和右半部分
状态计算
在每一种切法中取一个最小值，然后再对所有切法取一个最小值即可。
#include#include #include #include using namespace std; const int N = 15, M = 9; const double INF = 1e9; int n, m = 8; int s[M][M]; double f[M][M][M][M][N]; double X; // 表示x的平均值 // 那个公式的计算 double get(int x1, int y1, int x2, int y2) { double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] - X; return sum * sum / 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 = INF; 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 i = y1; i < y2; i++) // 竖切 { v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2)); // 取左边 v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i)); // 取右边 } return v; } int main() { cin >> n; for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) { cin >> s[i][j]; s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; } memset(f, -1, sizeof f); // double数组是使用科学计数法存储，当值为-1表示的是-NAN X = (double) s[m][m] / n; printf("%.3lfn", sqrt(dp(1, 1, 8, 8, n))); return 0; }
