区间 DP
- 合并小区间的最优解，得到大区间的最优解
eg1 ：合并石子
solution :
合并
- 我们想到， 区间 dp 一重要的特点是将区间合并
- 考虑最后边界， 是两由连续石子构成的小堆合成一大堆
- 那么我们就需要枚举每一个分界点
状态转移
- 最优子结构 ： 把 l - r 通过 l - i 与 i - r 合成一堆, 肯定是代价小的比代价大的好
可设 dp[l][r] 表示合并下标位置 l 到 r 的所有元素合并能获得的价值的最大值
可得转移方程
f[i][j] = min(f[i][k] + f[k][j], f[k + 1][j], sum[i][j])
( k 为断点 )
- 无后效性 ：先后枚举区间长度 len ， 区间起点 i (可推出终点 j = i + len - 1), 断点 k
for(int len = 2; len <= n; ++len)
for(int i = 1; i <= n - len + 1; ++i){
int j = i + len - 1;
for(int k = i; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
}
eg2 : 合并石子 但是围成一圈
soluiton :
破环成链(优化)
-
任取一个位置断开， 然后将序列复制一份粘在末尾
-
这样从任意一个位置断开得到的序列， 都与 f[1+ k][n + k] 之一对应 (0 \le k < n)
-
所有对于长度为 2n 的序列进行上述区间 dp, 枚举区间长度至 n
eg3 : 最长括号匹配子序列
solution :
设 f[i][j] 表示区间 [i, j] 中能取出的最长的括号匹配子序列长度
- [A]
- (A)
- AB
我们现在为上述三种情况考虑转移方程 :
-
如果 s[i] 与 s[j] 匹配 则
f[i][j] = f[i + 1][j - 1] + 2 -
`f[i][j] = max(f[i][k] + f[k + 1][j]), (i \le k < j)
考虑边界 : f[i][i] = 0
eg4 : 最少添加括号使匹配
solution :
最小添加括号数 = 总字符数 - 最长括号匹配子序列长度
eg5 : 最小矩阵合并时间复杂度
solution :
同石子合并 用 f[i][j] 表示从 i 到 j 所有矩阵合并的代价
eg6 : P1063 [NOIP2006 提高组] 能量项链
soluiton :
破环成链
同上
设 f[i][j] 表示从 i 到 j 所有区间合并的代价
eg7 : P4170 [CQOI2007] 涂色
soluiton :
设$f[i][j] 表示将区间 [i, j]$ 染完所花的最少次数
初始状态 : f[i][i] = 1
-
若 a[i] == a[j] 则
f[i][j] = min(f[i][j - 1], f[i + 1][j]) -
枚举断点
f[i][j] = min(f[i][k] + f[k + 1][j]), (i \le k < j)
eg8 : Halloween Costumes
小明要去参加 n 个派对，每个派对需要的服装种类在 1 - m 之间。（即 c_i 代表第 i 个派对需要的服装种类， 1 \le c_i \le m ）对于每一种派对，小明要穿对应的服装。
小明可以同时穿多个服装，且只有穿最外面的衣服会被看见。小明可以随时脱掉最外面的服装，或者穿上任意服装。但是脱掉的服装小明以后不会再穿，求小明最少要准备多少件服装。
一共有 T 个数据输入，每个输入包含： N, M ，以及 c_1, c_2, ... c_n 。（ T \le 2500 ）
solution :
同上
若一件衣服从第 i 天穿上, 到第 j 天脱下, 相当于将区间 [i, j] 染色
eg9 :P4302 [SCOI2003] 字符串折叠
soluiton :
用 f[i][j] 表示 [i, j] 这个区间内最小的长度 (f[i][i] = 1)
考虑转移的所有策略 :
-
区间 DP 枚举分割点
f[i][j] = min(f[i][k] + f[k + 1][j]) -
折叠当前区间 :
f[i][j] = min(f[i][j], f[i][k] + 2 + m[l / len])
即枚举区间长度的所有约数, 判断当前区间能否按此长度折叠
优化 : 使用 KMP 找出区间最小循环节
eg10 : P2858 [USACO06FEB] Treats for the Cows G/S
solution :
设 f[i][j] 表示盒子里还剩 i 到 j 区间时能收获的最大钱数 (f[i][N] = 0)
-
f[i][j] = max(f[i - 1][j] + day \times V[i - 1], f[i][j + 1] + day \times v[j + 1])
-
ans = max(f[i][i] + V[i] \times N)
eg11 : P1005 [NOIP2007 提高组] 矩阵取数游戏
soluiton :
-
由于每一行相互独立
-
同上
eg12 : P3205 [HNOI2010] 合唱队
solution :
设 f[i][j][0 / 1] 表示盒子里还剩 i 到 j 区间时排成, 且最后排进的为 i / j 的总数
f[i][j][0] = f[i + 1][j][0] * (a[i] < a[i + 1] ? 1 : 0) + f[i + 1][j][1] * (a[i] < a[j] ? 1 : 0)f[i][j][1] = f[i][j - 1][0] * (a[j] > a[i] ? 1 : 0) + f[i][j - 1][1] * (a[j] > a[j - 1] ? 1 : 0)
小组成员: 邵品渊，邵品砚，蒋佳成，顾天泽