- 10.3
- P2679
- 很容易想到定义状态 \(f_{i,j,k}\) 表示匹配到了 s 的第 \(i\) 个字符，t 的第 \(j\) 个字符用了 \(k\) 个串的方案数
- 然后你就会发现爆空间了
- 这时候我们可以使用滚动数组滚动第一维，令 \(f_{i,j,0/1}\) 表示匹配到了 t 的第 \(i\) 个字符，用了 \(j\) 个串，\(j\) 是否匹配的是 \(i-1\) 的方案数
- P5329
- 你会发现当有 连续一段相同字符的时候，删掉哪一个最后形成的字符串是相等的，但是由于我们要按 \(i\) 从小到大排序，故它们的编号是连续的
- 所以我们把问题转换为了相邻字母互不相同的时候该怎么排序
- 很显然的一件事，当第二个字符大于第一个字符的时候，那 \(s_1\) 就是最大的，否则就是最小的，以此类推即可
- P3080
- 我们很容易地可以发现每次必定是一个连续的区间故可以考虑区间DP
- 定义 \(f_{i,j,0/1}\) 为弄完 \(i-j\) 最后留在 \(i/j\) 的最小代价
- P4265
- 很显然可以定义 \(f_{i,j}\) 表示到第 \(i\) 块地砖，用的是第 \(j\) 双鞋是否可行
- 转移即可，用发散型 dp 感觉更好转移
- P2886 倍增floyd，矩阵加速
- 我们发现在 floyd 的转移中 \(f_{i,j} = \min(f_{i,k}+f_{k,j})\)
- 如果定义 \(a_{i,j}\) 为在钦定走 \(x\) 条边的情况下 \(i\) 到 \(j\) 的最短长度，\(b\) 钦定为 \(y\) 条边
- 那么若 \(f_{i,j}\) 表示的是第 \(x+y\) 条边的话那就有 \(f_{i,j} = \min(a_{i,k}+b_{k,j})\) 我们就可以使用矩阵快速幂进行转移
- 因为 \(\min\) 运算具有结合律
- P1800
- 一眼可以二分，定义 \(f_i\) 为第一个公司做了 \(i\) 个的时候第二个公司已经做了的模块的最大数，转移即可
- P2679