面向tg选手的DP练习题 笔记

0. 题单链接

1. P4310 绝世好题

做题心得

有二进制考虑拆位。

转移和二进制有关，故考虑用二进制的每一位设计状态转移方程。

设 $f_{i,j}$ 表示前 $i$ 个数，$j$ 这一位为 $1$ 的最长序列长度。

$$f_{i,j}=\underset{l=1}{\overset{n}{max}}\{f_{i-1,l}+1\}(a_l\text{ and }j=1)$$

答案为 $\underset{j=0}{\overset{\log a}{max}}\{f_{n,j}\}$

时间复杂度 $O(n\log a)$。（$a$ 为值域）

2. P1944 最长括号匹配

这题和 DP 有关系吗。

用一个栈处理，设 $vi{s}_i=0/1$ 表示第 $i$ 位能否匹配，在 $vis$ 中找到最长的连续 $1$ 的块即可。

时间复杂度 $O(n)$。（$n$ 为字符串长度）

3. P1772 [ZJOI2006] 物流运输

做题心得

问题复杂时，从简单入手，考虑特殊情况。

数据范围很小，考虑乱搞。

设 $f_i$ 表示第 $i$ 天的最优方案，$cos{t}_{i,j}$ 表示第 $i$ 到 $j$ 天都不改变航线的最小花费。

$$f_i=\underset{j=0}{\overset{i-1}{min}}\{f_j+cos{t}_{j+1}+k\}(f_0=-k)$$

这一部分时间复杂度 $O(n^2)$。

接着考虑 $cost$，直接在输入的时候暴力记录 $il{l}_{i,j}$ 表示 $i$ 号码头第 $j$ 天的不可用状态，然后 $O(n^2)$ 循环枚举第 $i\sim j$ 天，$O(nm)$ 循环枚举某一个码头在 $i\sim j$ 这一段时间里是否出现过不可用的状态，然后 $O(e\log m)$ 跑最短路。

答案为 $f_n$。

整体时间复杂度 $O(n^2+n^{3}m+n^{2}e\log m)$，T 不了一点。

4. P1284 三角形牧场

做题心得

可以通过已知信息优化状态数。

校内 OJ 有一题三个杯子互相倒水，就是用 $f_{a,b,c}$ 表示状态，其中 $a,b,c$ 分别是三个杯子里水的数量。

同理，设 $f_{i,a,b,c}$ 表示前 $i$ 条边，能否组成 $a,b,c$ 这样的三条边（先不考虑其是否为三角形）。

显然 MLE，但是由于每一条边都要用上，所以我们可以省略掉一维，用总和减两边得到第三边长，变为 $f_{i,a,b}$。

$$f_{i,a,b}=f_{i-1,a-l_k,b}\text{ or }{f}_{i-1,a,b-l_k}\text{ or }{f}_{i-1,a,b}(f_{0,0,0}=1)$$

$O(m^2)$ 枚举两边搭配是否存在方案即可，然后海伦公式直接算，取个 $max$。

5. P4158 [SCOI2009] 粉刷匠

做题心得

问题复杂时，先考虑部分，再考虑整体。

设 $g_{i,j}$ 表示前 $i$ 条刷 $j$ 次的最大正确数，但是我们显然要知道某一条刷若干次的最大正确数，才能求解 $g$。

设 $f_{i,k}$ 表示第 $i$ 条刷 $k$ 次的最大正确数，按照 DP 的定义这显然是难以转移的，我们再引入一维 $j$，设 $f_{i,j,k}$ 表示第 $i$ 条前 $j$ 格刷 $k$ 次的最大正确数，同时用前缀和 $s_{0/1,i,j}$ 求一下第 $i$ 条前 $j$ 格 $0/1$ 的数量。

$$f_{i,j,k}=\underset{l=1}{\overset{j-1}{max}}\{f_{i,l,k-1}+max(s_{0,i,j}-s_{0,i,l},s_{1,i,j}-s_{1,i,l})\}$$

需要注意的是，一次最少涂一格，所以 $k$ 的上界是 $m$ 而不是 $t$，时间复杂度是 $O(n{m}^3)$ 而非 $O(n{m}^{2}t)$。

$$g_{i,j}=\underset{k=1}{\overset{min(j,m)}{max}}\{g_{i-1,j-k}+f_{i,m,k}\}$$

答案为 $g_{n,t}$。

整体时间复杂度 $O(n{m}^3+nmt)$。

6. P1156 垃圾陷阱

巨大坑点：一个时间点可以存在多个垃圾。

设 $d{p}_{i,j,0/1}$ 表示表示在第 $i$ 个时刻，还能活 $j$ 个时刻（不包括第 $i$ 个时刻）的最大高度，$0$ 和 $1$ 表示当前垃圾是否使用，用于滚动数组。

设 $maxt$，$maxf$ 分别表示最大可能达到的 $i$ 和最大可能达到的 $j$。

则先把上一时刻的状态转移过来：

$$d{p}_{i,j,0}=max(d{p}_{i-1,j+1,0},d{p}_{i-1,j+1,1})$$

然后处理吃掉当前垃圾的情况：

$$d{p}_{i,j,1}=max(d{p}_{i,j,1},d{p}_{i,j-f,0})$$

然后处理用当前垃圾来垫高的情况：

$$d{p}_{i,j,1}=max(d{p}_{i,j,1},d{p}_{i,j,0}+h)$$

最后滚动数组合并：

$$d{p}_{i,j,0}=max(d{p}_{i,j,0},d{p}_{i,j,1})$$

找答案：

如果能垫上去，那么答案就是出现 $d{p}_{i,j,0}\ge D$ 时，$i$ 的最小值。

如果垫不上去，那么答案就是当存在 $d{p}_{i,j,0}$ 这种状态时，$i+j$ 的最大值。

时间复杂度 $O(FGT)$。

7. P4095 [HEOI2013] Eden 的新背包问题

（歪解，正解 CDQ）

首先，很明显是一个多重背包，按照多重背包的二进制拆分方式得到 $v$（价格），$w$（价值）。

假设第 $i$ 个物品拆分出来之后，在 $v$ 数组占据 $[l{t}_i,r{t}_i]$ 一段。开两个背包，$f_{i,j}$ 表示前 $i$ 个拆分出来的物品，最多花 $j$ 元的最大价值；$g_{i,j}$ 表示第 $i$ 个及以后拆分出来的物品，最多花 $j$ 元的最大价值。

1. 将上一个物品的状态转移过来

$$f_{i,j}=f_{i-1,j}$$

2. 背包

$$f_{i,j}=max(f_{i,j},f_{i-1,j-v_i}+w_i)$$

3. 由于 $j$ 表示最多花 $j$ 元，所以还需要将花了 $[0,j-1]$ 元的状态转移过来

$$f_{i,j}=max(f_{i,j},f_{i,j-1})$$

4. 从后往前做的背包同理：

$$g_{i,j}=g_{i+1,j}$$$$g_{i,j}=max(g_{i,j},g_{i-1,j-v_i}+w_i)$$$$g_{i,j}=max(g_{i,j},g_{i,j-1})$$

对于每一个询问（删掉物品 $d$ 而你有 $e$ 元），答案为：

$$\underset{i=0}{\overset{e}{max}}{f}_{l{t}_d-1,i}+g_{r{t}_d+1,e-i}$$

时间复杂度 $O({10}^3\times n\log c+qe)\approx O(3\times {10}^8)$

8. P2340 [USACO03FALL] Cow Exhibition G

设 $O=400\times [1000-(-1000)]÷2=4\times {10}^5$，$d{p}_i$ 表示当智商为 $i-O$ 时，情商的最大值。

若 $s_i\ge 0$，反着 01 背包：

$$d{p}_j=max(d{p}_{j-s_i}+f_i)$$

若 $s_i\le 0$，正着 01 背包：

$$d{p}_j=max(d{p}_{j+s_i}+f_i)$$

答案即为 $\underset{i=O}{\overset{8\times {10}^5}{max}}\{i-O+d{p}_i\}[d{p}_i\ge 0]$。

时间复杂度 $O(8\times {10}^5\times n)$。

10. P3188 [HNOI2007] 梦幻岛宝珠

做题心得

当题目有地方与思路冲突时，考虑寻找性质，转换冲突的地方，使得更好处理。

物品数很少，体积很大，但 $a,b$ 又很小，这启示可以按 $b$ 分组做 $0/1$ 背包。设 $f_{i,j}$ 表示 $b=i$ 的物品中，拿 $j\times 2^b$ 体积的物品的最大价值；设第 $k$ 个物品体积 $v_k=a_k\times 2^{b_k}$，价值为 $w_k$。

$$f_{i,j}=\underset{b_k=i}{max}\{f_{i,j-a_k}+w_k\}$$

接着考虑合并背包，有个重要的性质：

• 若接下来只考虑体积为 $k\times 2^i$ 的物品，则对于一部分体积总和小于 $a\times 2^{i-1}$ 的物品，其等价于一个体积为 $\lceil a÷2\rceil \times 2^i$ 的物品。

  • 感性理解一下，将背包划分为若干个大小为 $2^i$ 的格子，有个格子但凡被占用了 $1$ 的体积，它也不能再放 $2^i$ 体积的物品，如果 $i$ 从小到大考虑，一填就必须填满一个格子，那么就不存在能够填前面空格的情况。

但还有个问题，$W\ne a\times 2^b$，可以把 $W$ 二进制拆分为 $2^i+2^j+\cdots +2^k$ 的形式，如果 $W$ 的第 $i$ 位为 $1$，就说明多了一个大小为 $2^i$ 的格子，这个格子显然不会对大小为 $2^{i+1}$ 及更大的格子造成影响，故第 $i$ 位时可以丢一个 $2^i$ 进这个格子，不必合并到 $i+1$ 位。

有点抽象，结合公式理解，在上面 dp 的基础上，还要先合并。为了符合逻辑方便书写，我使用的是由 $f_{i,j}$ 转移到别的状态的写法。

$$p=max(\lfloor (j-((W÷2^i)\mathrm{and}1))÷2\rfloor ,0)$$$$f_{i+1,p}=max(f_{i+1,p},f_{i,j})$$

最后的答案，假设 $W$ 最高二进制位位 $s$，则为 $max(f_{s,1},f_{s,0})$，因为很有可能下面更小的格子全都找到了自己别的“归宿”，根本就没有人占用最高位的这一个格子。

状态数 $O(30\times 10\times n)$，转移复杂度 $O(n)$，总时间复杂度 $O(300n^2)$。

14. P2224 [HNOI2001] 产品加工

设 $f_{x,i}$ 表示加工到第 $x$ 个产品时，A 机器工作到时刻 $i$，B 机器工作到的时刻的最小值。

给 A 做，$f_{x,i}\leftarrow f_{x-1,i-a_i}$。

给 B 做，$f_{x,i}\leftarrow f_{x-1,i}+b_i$。

一起做，$f_{x,i}\leftarrow f_{x-1,i-c_i}+c_i$。

显然 $x$ 这一维可以直接扔掉变为 $f_i$，初始时 $f_i=\mathrm{\infty }$，$f_0=0$。当处理到第 $x$ 个产品时，$i$ 的上界 $maxx\leftarrow \sum _{p=1}^{x}max(a_i,c_i)$

答案为 $\underset{i=0}{\overset{maxx}{min}}\{max(i,f_i)\}$。

时间复杂度 $O(n^2)$。

15. P2851 [USACO06DEC] The Fewest Coins G

给钱是一个多重背包，找钱是一个完全背包，设 $f_i$ 表示给 $i$ 元最少需要的钱币数，$g_i$ 表示找 $i$ 元最少需要的钱币数。

dp 完之后，答案就是 $\underset{i=t}{\overset{max}{min}}\{f_i+g_{i-t}\}$。

时间复杂度 $O(N(T+V^2))$。

17. P4170 [CQOI2007] 涂色

做题心得

寻找条件转换题意为熟悉的模型。

挺板一区间 dp，设 $f_{i,j}$ 表示将 $[l,r]$ 涂成一种颜色的最小次数。

对于扩展区间，在本题中的实际意义就是提前涂好一层底色，再进行操作。

若 $co{l}_l=co{l}_r$，直接 $O(1)$ 转移：$f_{l,r}=min(f_{l+1,r},f_{l,r-1})$。

否则 $O(n)$ 枚举断点转移：

$$f_{l,r}=min\{f_{l,mid}+f_{mid+1,r}\}$$

时间复杂度 $O(n^3)$。

18. P2890 [USACO07OPEN] Cheapest Palindrome G

板区间 dp，设 $f_{i,j}$ 表示 $[i,j]$ 变成回文串的最小花费，初始时 $\mathrm{\forall }{s}_i=s_{i+1},f_{i,i+1=0}$；$\mathrm{\forall }i,f_{i,i}=0$。若 $i<j$

• $s_i=s_j$，不管：$f_{i,j}=f_{i+1,j-1}$。

• $s_i\ne s_j$，四种情况：结尾增 $i$，开头删 $i$，开头增 $j$，结尾删 $j$。

$$f_{i,j}=min(f_{i+1,j}+min(ad{d}_i,de{l}_i),f_{i,j-1}+min(ad{d}_j,de{l}_j))$$

答案为 $f_{1,n}$，时间复杂度 $O(n^2)$。

19. CF149D Coloring Brackets

做题心得

当实在难以转移时，合理添加状态。

先预处理出每个括号匹配的另一半，记与 $i$ 匹配的位置时 $ma{t}_i$。设 $f_{l,r}$ 表示 $[l,r]$ 内的答案总数，这并不好写，所以继续暴力开状态，设 $f_{l,r,0/1/2,0/1/2}$ 表示当 $l$ 颜色为无/红/蓝，$r$ 颜色同理时，$[l,r]$ 内的答案数。

• $\underset{l}{(}\underset{r}{)}$：直接 $f_{l,r,i,j}=1$，注意 $i,j$ 必有一个无色，必有一个有色。

• $\underset{l}{(}\dots \underset{r}{)}$：从 $[l+1,r-1]$ 转移，对于这里面区间两端取不同颜色，属于加法原理，注意 $(l,l+1),(r,r-1)$ 颜色不同，且 $(l,r)$ 必有一个无色，必有一个有色。

• $\underset{l}{(}\dots \underset{ma{t}_l}{)}\dots \underset{r}{)}$：从 $[l,ma{t}_l]$ 与 $[ma{t}_l+1,r]$ 转移，这里则是乘法原理，注意 $ma{t}_l,ma{t}_l+1$ 颜色不同。

正着写从小到大的区间 dp 有很多不合法的情况且 TLE，所以可以写成记忆化搜索。

答案为 $\sum _{i=0}^2\sum _{j=0}^2{f}_{1,n,i,j}$，这玩意时间复杂度似乎不超过 $O(n\log n)$，不会证（逃。

20. P5851 [USACO19DEC] Greedy Pie Eaters P

做题心得

寻找区间内独有的情况，处理出这种情况的结果，然后区间 dp 计算方案。

区间 dp，设 $f_{i,j}$ 表示吃完 $[i,j]$ 的派的最优值，则可以板区间 dp：

$$f_{l,r}=\underset{mid=l}{\overset{r-1}{max}}\{f_{l,mid},f_{mid+1,r}\}$$

也有可能有一头牛吃完了这个区间的最后一个派，假设这个派的位置是 $mid$：

$$f_{l,r}=\underset{mid=l}{\overset{r}{max}}\{f_{l,mid-1}+f_{mid+1,r}+g_{l,r,mid}\}$$

$g_{l,r,mid}$ 表示 $[l,r]$ 区间最后吃 $mid$ 的最大牛，原因是一种方案内，符合下标条件的牛一定只有一条，故可以贪心取最大，初始输入 $w,l,r$ 时，$\mathrm{\forall }i\in [l,r],g_{l,r,i}=w$，然后这区间可以 $O(1)$ 扩展。区间 $[l,r]$ 第 $i$ 个最后被吃，要么是 $g_{l,r-1,i}$ 这头牛吃，要么是 $g_{l+1,r,i}$ 这头牛吃，注意 $i$ 是否在分割的小区间内，总的即：

$$g_{l,r,i}=max(g_{l,r-1,i}[i\ne r],g_{l+1,r,i}[i\ne l])$$

答案为 $f_{1,n}$，时间复杂度 $O(n^3)$。

21. UVA1437 String painter

首先，这题相当于染色的加强版。

考虑从空到 $b$ 的方案，求法与染色相同。加入 $a$ 之后，就变成了不是 $f_{1,n}$ 最优，而是 $(f_{1,i}+f_{i+1,j}+\cdots +f_{k+1,n})$ 最优，因为有的字母如果与 $a$ 相同，可以不涂，由此产生许多其他情况。而求上面式子，$O(n^2)$ dp 即可，设 $g_i$ 表示前 $i$ 个字母，$a$ 变成 $b$ 的最小次数。

• 先赋初值，直接从 $1$ 涂过来：$f_{1,i}$。

• 如果 $a_i=b_i$，这位可以不涂：$min(g_i,g_{i-1})$。

• 从前面转移：$\underset{j=1}{\overset{i-1}{min}}\{g_j+f_{j+1,i}\}$。

$g_i$ 就是上面三个的最小值，答案为 $g_n$，时间复杂度 $O(n^3+n^2)$。

22. UVA1629 切蛋糕 Cake slicing

状态这么小直接记忆化爆搜，用二维前缀和处理每个区间内樱桃个数即可，$f(u,d,l,r)$ 表示一个矩形区间最小花费，枚举从哪切割，横切还是竖切，递归子区间即可

$$f(u,d,l,r)=\{\begin{array}{ll}0& \mathrm{区}\mathrm{间}\mathrm{内}\mathrm{恰}\mathrm{有}1\mathrm{个}\mathrm{樱}\mathrm{桃}\\ \mathrm{\infty }& \mathrm{区}\mathrm{间}\mathrm{内}\mathrm{无}\mathrm{樱}\mathrm{桃}\\ min(\underset{mid=u}{\overset{d-1}{min}}f(u,mid,l,r)+f(mid+1,d,l,r)+r-l+1,\underset{mid=l}{\overset{r-1}{min}}f(u,d,l,mid)+f(u,d,mid+1,r)+d-u+1)& \text{Otherwise.}\end{array}$$

答案为 $f(1,n,1,m)$，时间复杂度为状态数加上二维前缀和：$O(n^3+n^2)$。