区间动态规划

区间类动态规划的问题解法比较固定：以区间长度为阶段，枚举区间长度，再枚举区间左端点，之后再枚举区间断点进行转移。

AcWing 282. 石子合并

分析：若最初的第 $l$ 堆石子和第 $r$ 堆石子被合并成一堆，则说明 $l\sim r$ 之间的每堆石子也已经被合并，如此 $l$ 和 $r$ 才有可能相邻。因此，在任意时刻，任意一堆石子均可以用一个闭区间 $[l,r]$ 来描述，表示这堆石子是由最初的第 $l\sim r$ 堆石子合并而来，其重量为 $\sum _{i=l}^r{A}_i$。

另外，一定存在一个整数 $k(l\le k<r)$，在这堆石子形成之前，先有第 $[l,k]$ 堆石子被合并成一堆，第 $[k+1,r]$ 堆石子被合并成一堆，然后这两堆石子才合并成 $[l,r]$。

对应动态规划中，这就意味着两个长度更小的区间上的信息转移到更长的区间上，划分点 $k$ 就是转移中的决策，这样我们以区间长度作为阶段，由于区间长度可以通过左右端点计算得来，因此设 $f(l,r)$ 表示把最初的第 $l$ 堆到第 $r$ 堆合并成一堆，需要消耗的最小体力。

$f(l,r)=\underset{l\le k<r}{min}\{f(l,k)+f(k+1,r)\}+\sum _{i=l}^r{A}_i$

边界条件：$f(l,l)=0$，其余为 $+\mathrm{\infty }$

目标解：$f(1,n)$

#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int s[N];
int f[N][N];
int n;

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

	for (int len = 2; len <= n; len++) {
		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++) {
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
			}
		}
	}

	cout << f[1][n] << endl;

	return 0;
}

AcWing 1068. 环形石子合并

与上例不同的是：这里的石子是围成了一个环

分析：由上题思考，对于环形相邻问题一般有两种解决办法：

1. 枚举环分开的位置，将环还原成链。时间复杂度 $O(n^4)$
2. 将[[链延长两倍。]]时间复杂度为 $O(n^3)$

涉及到圆环。我们可以用“破环成链”。一般使用第二种方案：链的长度是环的两倍，我们在 $[1,2\ast n]$ 的区间范围内进行计算。

#include <bits/stdc++.h>
using namespace std;

const int N = 210 * 2;
int a[N], s[N];
int f[N][N], g[N][N]; // f 存储最大值，g存储最小值
int n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[n + i] = a[i];
	}
	for (int i = 1; i <= 2 * n; i++) s[i] = s[i - 1] + a[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;
	    	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 maxv = -0x3f3f3f3f, minv = 0x3f3f3f3f;
	for (int l = 1; l <= n; l++) {
		maxv = max(maxv, f[l][l + n - 1]);
		minv = min(minv, g[l][l + n - 1]);
	}
	cout << minv << endl << maxv << endl;

	return 0;
}

洛谷 P1063：能量项链

分析：这道题每一个珠子的首尾可以看成是一个矩阵的左右两端点，合并两个珠子 $(a,b),(b,c)$ 的操作就像是矩阵乘法一样，合并完后就变成了 $(a,c)$ 因此我们可以离散的来存储每个参数。如 $(a,b),(b,c),(c,a)$ 存储为 $(a,b,c,a)$

设 $f(l,r)$ 表示将区间 $[l,r]$ 合并成一个区间（珠子）的获得的最大能量

$f(l,r)=max(f(l,k)+f(k,r)+w[l]\ast w[k]\ast w[r])(l<k<r)$

为什么这里的是 $k$ 而不是之前的 $k+1$ 呢？本题合并珠子时，分割点 $k$ 要被分到左侧区间的右端点和右侧区间的左端点中。因此，参数 $k$ 要作为两个区间的共同端点来使用，此外我们原来只需要合并 $n$ 个珠子，这样转换后就要合并 $n+1$ 个珠子了

边界条件：$f[i][i+1]=0$，区间长度为 $2$ 时无法释放能量

目标解：$f[i][i+n]$

#include <bits/stdc++.h>
using namespace std;

const int N = 210;
int a[N], f[N][N];
int n;

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

	// 长度从 3 开始，长度为 2 时无法释放能量
	for (int len = 3; len <= n + 1; len++) {
	    for (int i = 1; i + len - 1 <= 2 * n; i++) {
	        int l = i, r = i + len - 1;
	        // 分界点是从 l + 1 开始的
		    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 res = 0;
	for (int l = 1; l <= n; l++) {
		res = max(res, f[l][l + n]);
	}
	cout << res << endl;

	return 0;
}

AcWing 1069. 凸多边形的划分

总结与习题

总结

区间 DP 的基本特征是能将问题分解成为两两合并的形式。解决方法是区间长度为阶段，枚举划分点，将问题分解成为左右两个部分，合并最后的两个部分的最优解得到原问题的最优解。

状态转移方程一般形式如下：$f[i][j]=max\{f[i][k]+f[k+1][j]+\mathrm{决}\mathrm{策}\mathrm{值}\}$ $k$ 为划分点

习题

请使用区间 DP 的思考方式完成以下两题：

1. AcWing 1026. 乘积最大
2. 洛谷 P1281：书的复制