区间DP题目_hecy 又接了个新任务:be 处理。be 中有一类被称为 gbe。 以下是 gbe 的定义: 空表

括号配对

Hecy 又接了个新任务：BE 处理。

BE 中有一类被称为 GBE。

以下是 GBE 的定义：

空表达式是 GBE
如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
如果 A 与 B 都是 GBE，那么 AB 是 GBE
下面给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。

注意：BE 是一个仅由(、)、[、]四种字符中的若干种构成的字符串。

输入格式
输入仅一行，为字符串 BE。

输出格式
输出仅一个整数，表示增加的最少字符数。

数据范围
对于所有输入字符串，其长度小于100。

输入样例：

[])

输出样例：

1

闫氏DP分析法

方法一：基本思路
添加若干的字符使其达到匹配的目的 等价于 将不匹配的字符去除 使得字符串达到匹配的目的
所以这题只是计算出已配完成的括号数 再用总长度减去 就是不匹配的字符长度 即为答案

关于DP的状态表示和状态计算

1. 关于状态表示
   a. 集合： L,R区间内括号匹配数目的集合
   b. 属性： max

2. 状态计算
   划分为2个部分
   a. 选择L,R端点 f[L][R]=f[L+1][R-1]+1;(s[L]==s[R])
   b. 不全选L,R端点 f[L][R]=max(f[L][R],f[L][k]+f[k+1][R]);
   对于a部分比较好理解 L,R端点均选择时如果相等则结果+1
   对于b部分
   以左端点为例 不选L的可能性包含于L+1~R的所有集合中 同理只选右端点 和两个端点都不选的情况也是一样的

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
char s[N];
int f[N][N];
int main()
{
	cin >> s;
	int n = strlen(s);
	for (int len = 1; len <= n; len ++ )
		for (int l = 0; l + len - 1 < n; l ++ ) {
			int r = l + len - 1;
			// 第一种：l和r被选择
			if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')) 
				f[l][r] = f[l + 1][r - 1] + 1;
			// 第二种：l和r不全选
			for (int k = l; k < r; k ++ ) 
				f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r]);
		}
	cout << n - f[0][n - 1] * 2;
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二

老样子按照dp步骤来：老样子按照dp步骤来：

1.状态定义: dp(i,j)表示区间[i,j]中添加字符使其成为GBE的集合，属性为min1.状态定义:dp(i,j)表示区间[i,j]中添加字符使其成为GBE的集合，属性为min

2.状态转移（这一步比较难）：2.状态转移（这一步比较难）：
这个集合由哪些组成呢？按照最后不同的一步来，假如i与j匹配，只需要从dp(i+1,j−1)那个集合转移过来
这个集合由哪些组成呢？按照最后不同的一步来，假如i与j匹配，只需要从dp(i+1,j−1)那个集合转移过来

假如不匹配，那似乎应该从dp(i+1,j)或者dp(i,j−1)dp(i+1,j)或者dp(i,j−1)来,这里是最大的坑。

因为题目中有个条件是ABAB都是GBEGBE,那么ABAB也是。

那如果字符串是()[]，需要匹配是0个，但是第一个和最后一个是不匹配的，就会转移错误。

所以，我们需要枚举区间[i,j]里的每个分隔点，看是否会出现题目出现的第三种AB都是GBE所以，我们需要枚举区间[i,j]里的每个分隔点，看是否会出现题目出现的第三种AB都是GBE（第二种已经被包含），使得需要添加的更少。

dp(i,j)=dp(i+1,j−1)(s[i]==s[j])dp(i,j)=dp(i+1,j−1)(s[i]==s[j])
dp(i,j)=min(dp(i,j),dp(i,k)+dp(k+1,j))(i<=k<=j)dp(i,j)=min(dp(i,j),dp(i,k)+dp(k+1,j))(i<=k<=j)

3.初始化：
全部是INF，因为要取最小值，不合法的状态可以在递推的时候变成0，或者改变k的范围。但是在这道题全部是INF，因为要取最小值，不合法的状态可以在递推的时候变成0，或者改变k的范围。但是在这道题里，不影响。

或者：一开始全部为0，然后每次在到一个新的[i,j]区间时全部设成INF，这样不合法区间就为0，就不用特或者：一开始全部为0，然后每次在到一个新的[i,j]区间时全部设成INF，这样不合法区间就为0，就不用特判。

4.递推顺序：
因为要用到后面的状态，所以i要逆序枚举。因为要用到后面的状态，所以i要逆序枚举。

5.注意点：

1. 当枚举分割点的时候，已经不需要在看小区间内是否端点匹配了，因为更小的区间的最小值已经在之前更新过了。
2. 当i=j−1时，s[i]和s[j]match的时候，dp(i,j)应该为0，但是dp(i+1,j−1)为不合法状态为INF，2.当i=j−1时，s[i]和s[j]match的时候，dp(i,j)应该为0，但是dp(i+1,j−1)为不合法状态为INF，如果转移过来需要特判。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 100000000;

int n;
int f[N][N];

bool is_match(char l, char r)
{
    if (l == '(' && r == ')') return true;
    if (l == '[' && r == ']') return true;
    return false;
}

int main()
{
    string s;
    cin >> s;
    n = s.size();

    for (int len = 1; len <= n; len ++ )
        for (int i = 0; i + len - 1 < n; i ++ )
        {
            int j = i + len - 1;
            f[i][j] = INF;
            if (is_match(s[i], s[j])) f[i][j] = f[i + 1][j - 1];
            if (j >= 1) f[i][j] = min(f[i][j], min(f[i][j - 1], f[i + 1][j]) + 1);

            for (int k = i; k < j; k ++ )
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
        }

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

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

石子合并

设有 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≤N≤300

输入样例：

4
1 3 5 2

输出样例：

22

题意： 合并 N 堆石子，每次只能合并相邻的两堆石子，求最小代价

思路：

核心：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并

状态表示：f[i][j]f[i][j] 表示将 ii 到 jj 合并成一堆的方案的集合，属性 Min

状态计算：
(1) i<ji<j 时，f[i][j]=mini≤k≤j−1f[i][k]+f[k+1][j]+s[j]−s[i−1]f[i][j]=mini≤k≤j−1f[i][k]+f[k+1][j]+s[j]−s[i−1]
(2) i=ji=j 时， f[i][i]=0f[i][i]=0 （合并一堆石子代价为 0）

问题答案： f[1][n]f[1][n]

区间 DP 常用模版
所有的区间dp问题，第一维都是枚举区间长度，一般 len = 1 用来初始化，枚举从 len = 2 开始，第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）

for (int i = 1; i <= n; i++) {
    dp[i][i] = 初始值
}
for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
        int j = i + len - 1;                 //区间终点
        for (int k = i; k < j; k++) {        //枚举分割点，构造状态转移方程
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
1
2
3
4
5
6
7
8
9
10

#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int n;
int s[N], cou[N];
int f[N][N];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> s[i];
		cou[i] = cou[i - 1] + s[i];	
	}
	// 长度必须从2开始，如果从1开始后续会影响使得无法求最小值 
	for (int len = 2; len <= n; len ++ )
		for (int l = 1; l + len - 1 <= n; l ++ ) {
			int r = l + len - 1;
			f[l][r] = 1e8;
			// 以左右两堆中间的分界点进行枚举 
			// 以左堆的最后一堆为分界点进行枚举
			for (int k = l; k < r; k ++ )  
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + cou[r] - cou[l - 1]); 
		} 
	cout << f[1][n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

环形石子合并

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

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

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

输入格式
第一行包含整数 n，表示共有 n 堆石子。

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

输出格式
输出共两行：

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

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

数据范围

1≤n≤200

输入样例：

4
4 5 9 4

输出样例：

43
54

在考虑一下本题的 环形相邻 情况如何解决，方案有如下两种：
一般常用的都是第二种方法

1. 我们可以枚举环中分开的位置，将环还原成链，这样就需要枚举 n 次，时间复杂度为 O(n^4)
2. 我们可以把链延长两倍，变成 2n 个堆，其中 i 和 i+1 是相同的两个堆，然后直接套 区间DP 模板，但对于 阶段 len 只枚举到 n，根据 状态的定义，最终可以得到所求的方案，时间复杂度为 O(n^3)
   将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 410;
int n;
int a[N];
int f[N][N], g[N][N];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		a[i + n] = a[i];
	}
	// 延长区间为2n
	for (int i = 1; i <= n * 2; i ++ ) a[i] += a[i - 1];
	memset(f, 0x3f3f3f, sizeof f);
	memset(g, -0x3f3f3f, sizeof g);
	// 枚举长度仍然为n，但左端点可以到n，右端点可以到2n
	for (int len = 1; len <= n; len ++ ) 
		for (int l = 1; l + len - 1 <= n * 2; l ++ ) {
			int r = l + len - 1;
			if (l == r) 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] + a[r] - a[l - 1]);
					g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + a[r] - a[l - 1]);	
				} 
			}
		}
	int minv = 0x3f3f3f3f3f3f, maxv = -0x3f3f3f3f3f3f;
	for (int l = 1; l <= n; l ++ ) {
		minv = min(minv, f[l][l + n - 1]);
		maxv = max(maxv, g[l][l + n - 1]);
	}
	cout << minv << endl << maxv << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

能量项链

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

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

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

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

如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 m×r×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×2×3=60。

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

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

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

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

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

数据范围
4 ≤ N ≤ 100,
1 ≤ E ≤ 2.1 × 109

输入样例：

4
2 3 5 10

输出样例：

710

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n;
int a[N];
int f[N][N];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		a[i + n] = a[i];
	}
	// 以区间划分，3个数字才可以开始一次合并
	// 由于是链，长度多1 
	for (int len = 3; len <= n + 1; len ++ ) 
		for (int l = 1; l + len - 1 <= 2 * n; l ++ ) {
			int r = l + len - 1;
			// 以区间划分，划分点为左区间的右值，故最小为l+1 
			for (int k = l + 1; k < r; k ++ ) 
				// 以区间划分，k点为左右区间公用点 
				f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
		}
	int res = -0x3f3f3f3f3f;
	for (int l = 1; l <= n; l ++ ) res = max(res, f[l][l + n]);
	cout << res;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

加分二叉树

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

每个节点都有一个分数（均为正整数），记第 i 个节点的分数为 di，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

(区间DP,二叉树的遍历) O(n^3)
状态表示：f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值。
状态计算：f[i][j] = max(f[i][k - 1] * f[k + 1][j] + w[k])，即将f[i][j]表示的二叉树集合按根节点分类，则根节点在 k 时的最大得分即为 f[i][k - 1] * f[k + 1][j] + w[k]，则f[i][j]即为遍历 k 所取到的最大值。

在计算每个状态的过程中，记录每个区间的最大值所对应的根节点编号。

那么最后就可以通过DFS求出最大加分二叉树的前序遍历了。

时间复杂度
状态总数是 O(n^2)，计算每个状态需要 O(n) 的计算量，因此总时间复杂度是 O(n^3)。

#include <iostream>
using namespace std;
const int N = 35;
int n;
int w[N];
int f[N][N], g[N][N];
void dfs(int l, int r) 
{
	if (l > r) return;
	int k = g[l][r];
	cout << k << ' ';
	// 左子树 
	dfs(l, k - 1);
	// 右子树 
	dfs(k + 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];
					int right = k == r ? 1 : f[k + 1][r];
					int score = left * right + w[k];
					// 如果大于当前区间最高加分，则更新加分，更新根节点 
					if (f[l][r] < score) {
						f[l][r] = score;
						g[l][r] = k;
					}  
				}
			} 
		}
	cout << f[1][n] << endl;
	// （没懂）由于计算，则可以直接得出字典序最小的前序遍历 
	dfs(1, n);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45