区间DP总结
考试总结
Task 1
正解
性质题，找规律。
规律如下：
从 $n=15$ 开始：
$108,188,200,208,288,688,888,1088,1888,2008,2888,8888\dots$
容易发现 $a_n=a_{n-7}\times10+8\quad(n \geq 22)$
前14个要特判。
代码
1 | 无 |
关键点
暴力找规律。
死因
20 开头的规律没找到，就是没打暴力找规律。
Task 2
正解
搜索。
优化
这道题可以用 十字链表（Dancing Links X） 加速，但是爆搜就能跑出 $400\text{ms}$ 的好成绩。
别名：双向循环十字链表。
为什么能跑这么快
关键点：
- 对于这种搜索时间最不利的是 $5 \times 6$ 的矩阵，并且是无解的情况。
- 正常来说，如果不要求不能重复走点，时间复杂度最坏为 $O(2^{4} \times 3^{14} \times 4^{16})$ ，即四个角（4个）上的点有两种走法，边上的点（14个）有三种走法，内部的点（16个）有四种走法。
- 但是不能重复走点的情况下，时间复杂度最坏为 $O(1^{4} \times 2^{14} \times 3^{16})$，但是考虑到实际情况，加一个可行性剪枝，最后 $\text{dfs()}$ 函数大概只会运行到 $5 \times 10^6$ 次。
- 爆搜敢冲就能过。
题目来源
《永远的七日之都》
代码
1 | 无 |
死因
1 | for (int i = 0; i <= n; i++) // wssb |
Task 3
正解
以 $dp$ 为辅助的搜索题。
说真的，这道题不难。一切的思路都是自然而然的，从爆搜到可行性剪枝再到用 $dp$ 完成可行性剪枝，最后实现的代码难度也不高。
关键点
$dp$ 可能不是一道题的全部而是一道题的部分。
思路
- 先想爆搜，同一位按字典序从大到小搜，期望得分：$30-40;pts$。
- 再想剪枝，用 $dp$ 判定后面有没有可能有解，计算一个点后最多能获取到的权值，再加上已经搜到的权值看它能不能 $\geq x$ 。
- 怎么做 $dp$ ？记录 $dp$ 长度和最后一位，预处理 $dp$ 时间复杂度为 $O(4n)$ 。整个算法时间复杂度见课后思考。
课后思考
- 整体时间复杂度是 $O(n+k)$ 还是 $O(nk)$ ？理论分析应该是 $O(n+k)$ 。
代码
1 | 无 |
死因
并没有死，打了暴力。还是全场唯一得分点（$30;pts$）。
但是事实上我的暴力打得还有优化空间且有一个小问题。
Task 4
正解
区间 $dp$ 。
思路
- 考虑朴素区间 $dp$ ，对于每个 $l\sim r$ 区间，枚举小区间并转移，时间复杂度 $O(n^4)$ 。
- 但是这种做法会 $\text{WA}$ 掉，因为这样记录状态会有情况没考虑到。所以考虑重设状态 $f_{i,j,max,min}$ 表示区间 $i\sim j$ 内已经通过多次操作后剩下的最大值为 $max$ 、最小值为 $min$ 时，所花的最小代价。而后我们定义 $ans_{i,j}$ 为 $i\sim j$ 这段区间被选空的最终答案（就是题目中说的那个最后输出的答案）。
- 接下来考虑怎么转移。$ans_{i,j}$ 的转移很简单，就是 $ans_{i,j}=max(f_{i,j,max,min}+a+b\times(max-min))$ 。而 $f_{i,j,max,min}$ 的转移，首先应该枚举中间断点 $k$ 就应该有以下三种情况：
- $min$ 与 $max$ 都在左边，右边被选空：$f_{i,j,max,min}=f_{i,k,max,min}+ans_{k+1,j}$ 。
- $min$ 与 $max$ 都在右边，左边被选空：$f_{i,j,max,min}=ans_{i,k}+f_{k+1,j,max,min}$ 。
- $min$ 与 $max$ 左右两边都有：$f_{i,j,max,min}=f_{i,k,max,min}+f_{k+1,j,max,min}$ 。
- 容易发现的是，这样转移肯定不会少考虑情况，接下来就是考虑这么转移是否会多考虑情况？如果多考虑了，对答案有没有影响？
- 【这里不会】（zhw看到了comment一下）
- 结论：会多考虑情况但是这些情况不会比答案更优。
- 注意点：$w_i \leq 1000$ ，需要离散化处理。
来源
代码
1 | 无 |
区间DP总结
- 区间DP是变化之神！
- $\text{Link Start!}$
通过例题看看区间DP的一些套路和新的思路。
不如按题目分类来说。
A~E 普通/模板区间DP
- 能量项链——普通区间DP
- 石子合并（加强版）——四边形不等式优化（不要求掌握）
- 【USACO 3.3.5】A Game游戏 IOI’96——带了博弈论的区间DP（个人觉得有点意思）
- 做错的作业——括号匹配类型的区间DP
- 【CQOI 2007】涂色——涂色类型区间DP
F,G 凸多边形区间DP
这一类型的DP特点是建立模型比较难。
要点梳理：
- 无论从哪一个点开始都一样，因此不必拆环成链。
- 状态定义为：$f_{i,j}$ 表示将 $i\sim j$ 这一段点的区间转化为三角形的最小价值。
- 状态转移为：$f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k,j}+\text{cost}(i,j,k))$ ，即 $k$ 是两个子区间的公共端点， 而将他们合并后能组合出新的三角形 $\Delta A_iA_jA_k$ ，因此要加上这个新三角形造成的权值。
H 字符串折叠
我认为这道题的思路是捋得最清的，因为这道题真的很简单。
大致思路就是有两种转移：一是组合两段已压缩的区间，二是将这段区间压缩，时间复杂度大致为 $O(n^4)$ ，能刚刚好卡着过（据说用预处理或哈希或KMP找最长重复子串的长度能够将这道题卡到 $O(n^3)$ 的时间复杂度，然鹅我不会）。
R 压缩
这也是一道压缩字符串的题目。
但是这里对 $M$ 和 $R$ 的处理要更为复杂。
具体而言，这道题的 $f_{i,j,k}\quad(1\leq i\leq j\leq n,k\subset{0,1})$ 多了一维，用于标记 $i\sim j$ 这段区间内是（$1$）否（$0$）存在 $M$ 。
状态转移：
- $f_{i,j,0}=f_{i,k,0}+j-k$
- $f_{i,j,1}=\min(f_{i,k,0},f_{i,k,1})+\min(f_{k+1,j,0},f_{k+1,j,1})$
- $f_{i,j,0}=f_{i,mid,0}+1\quad\text{when }[i,j]\text{ can compress}$
J 表达式的亿种可能性
最有意义的题目之一。
维护的 $f_{i,j}$ 就是答案所求，关键就在转移。
弄清楚以下几点：
- $\times$ 的转移不需要别的东西，只需要 $f_{i,j}=f_{i,k}\times f_{k+1,j} \times\text{val}$
- $+$ 和 $-$ 的转移需要考虑左边的括号个数和右边的括号个数（详见第一次提交内的代码推导），最终转移式为：$f_{i,j}=((j-k-1)!f_{i,k}+(k-i)!f_{k+1,j})\times\text{val}$
- 但是以上转移式只考虑了先放完左边的括号再放右边的括号，然而，我们可以左右交替来回放，并且，左边内括号的顺序已经是我们在 $f_{i,k}$ 中内定好的了。因此 $\text{val}=\frac{(j-i-1)!}{(k-i)!(j-k-1)!}$ 作为系数。
M 有味道的数字
最具有启发性的一题。
这道题有几个性质需要搜索搜出来——只有 $3$ 和 $7$ 无法表示，表示 $5000$ 以内的数字最多只会用到长度为 $11$ 的前缀。
$f_{i,j}$ 表示 $i\sim j$ 这段区间内能表示出来的值（是个数组）这种思想有个很NB的名字叫做 **离散_____**（人话：打表）。
即用 $\text{vector}$ 存储值，单次转移时间复杂度就是 $O(nm)$ （ $n,m$ 表示合并的两个 $\text{vector}$ ） ，玄学下降！
而转移嘛……人人都会。
Q 单调栈
搜索最上牌面的一题。
这道题思路没什么好说的，只是注意一下有的时候记忆化搜索比循环区间DP好写。
区间DP的一点小知识
我个人一般会这么打区间DP：
1 | for (int len = 2; len <= n; len++) { |
然而这么打常数是比较大的，优化写法：
1 | for (int j = 2; j <= n; j++) { |
据说这样能优化很多。
我认为区间DP还有一类很重要的题，典型例题：关路灯
区间DP的特征
- 在操作中需要将两端区间合并，合并时存在固定的转移关系。
- 在操作中需要将子区间转移。
怎么看需不需要多开维数
很明显，当目前的状态定义会出现明显重复统计或是限制条件不够时要多开空间。