发现自己 DP 太差,于是做这个来坚实一下基础。

比赛链接

代码

洛谷上的题目列表

A Frog 1

签到题。设 $f(n)$ 为到第 $n$ 块石头的最小花费,那么 $f(n) = \min \{f(n - 1) + w(n - 1, n), f(n - 2) + w(n - 2, n)\}$,其中 $w(i, j) = |h_i - h_j|$。

B Frog 2

沿用上一题的状态,显然有 $f(i) = \min \limits_{j = k - i}^{i - 1} \{f(j) + w(i, j)\}$。

C Vacation

设 $f(i, 0/1/2)$ 为第 $i$ 天选择第 $0/1/2$ 种方式的收益,那么有:

$$ \begin{align} f(i, 0) = \max \{f(i - 1, 1), f(i - 1, 2)\} + w(i, 0) \\ f(i, 1) = \max \{f(i - 1, 0), f(i - 1, 2)\} + w(i, 1) \\ f(i, 2) = \max \{f(i - 1, 0), f(i - 1, 1)\} + w(i, 2) \\ \end{align} $$

答案为 $\max \{f(n, 0), f(n, 1), f(n, 2)\}$。

D Knapsack 1

背包模板题。

E Knapsack 2

仍然是 01 背包,但是此时 $W$ 太大,不能作为状态。

注意到物品价值很小,设 $f(i)$ 为价值为 $i$ 所需要的最小体积,那么有 $f(i) = \min \limits_{i - v \ge 0} \{f(i - v)\} + w$。初始化 $f(i) = \infty, f(0) = 0$。答案为满足 $f(i) \le W$ 的最大的 $i$。

F LCS

LCS 模板题。关键是这个输出方案有点麻烦。每次判断当前的 $f(i, j)$ 是从哪个状态转移来的,然后递归求解,当 $s_i = t_j$ 时将这个字符加入答案。

G Longest Path

由于图是 DAG,设当前点为 $u$,所有出边连向的点为 $v$,则有 $f(v) = \max f(u) + 1$。答案为 $\max \limits_{i = 1}^n \{f(i)\}$。

H Grid 1

设走到点 $(i, j)$ 的方案数为 $f(i, j)$,则有 $f(i, j) = f(i - 1, j) + f(i, j - 1)$。边界 $f(1, 1) = 1$。

I Coins

设 $f(i, j)$ 为有 $i$ 次向上,$j$ 次向下的概率,那么 $f(i, j) = f(i - 1, j) \cdot p_{i + j} + f(i, j - 1) \cdot (1 - p_{i + j})$。答案为 $\sum \limits_{i > j \land i + j = n} f(i, j)$。

J Sushi

第一道卡住的题目...主要对于智商不太够的人来说这个期望实在有点难理解...

由于盘子是不分先后的,我们可以考虑设 $f(i, j, k)$ 为当前有 $i$ 盘一个寿司,$j$ 盘两个寿司,$k$ 盘三个寿司的期望。不难发现吃到寿司的概率为 $\frac{i + j + k}{n}$。我们知道在这道题目中吃到寿司的价值为 $1$,那么可以得到 $E(X) = \frac{1}{P(X)} = \frac{n}{i + j + k}$。

接下来考虑从 $i + j + k$ 个盘子中选,显然应该有 $f(i, j, k) = \frac{i}{i + j + k} \cdot f(i - 1, j, k)$,同理可以列出 $j, k$ 的式子。

这个 DP 直接递推有点麻烦,可以用记忆化搜索解决。

K Stones

怎么日本人把博弈论当 DP 啊?

设 $f(i)$ 为剩下 $i$ 块石头时的胜负状态,如果 $f(i) = 0$,那么 $f(i + a) = 1$,因为在 $i + a$ 状态的玩家一定可以取走 $a$ 块石头来让自己获胜。边界 $f(0) = 0$。

可能有人会思考 $f(i)$ 如果从两个不同的状态转移而来会怎么样,其实不难发现只要有一个状态能赢,当前的玩家就一定选择这个状态,因为二人都是按照最优策略行动的。

L Deque

设 $f(i, j)$ 为取完 $[i, j]$ 的先手的最大收益,则答案为 $2f(1, n) - s(1, n)$,其中 $s(i, j) = \sum \limits_{i = i}^j a_i$。

考虑 $f(i, j)$ 怎么转移,我们发现取完 $[i, j]$ 内的分数是固定的。由于要最大化 $f(i, j)$,那么有 $f(i, j) = s(i, j) - \min \{f(i + 1, j), f(i, j - 1)\}$。边界 $f(i, i) = a_i$。

另外本题可以滚动数组优化,设 $f(i, j)$ 表示取完区间 $[i, i + j]$ 的先手的最大收益,此时的状态转移方程的第二维只和 $j - 1$ 有关,于是可以优化掉一维。

M Candies

朴素的 DP 很好想:设 $f(i, j)$ 为前 $i$ 个人分了 $j$ 块糖的方案数,转移为 $f(i, j) = \sum \limits_{t = 0}^{a_i} f(i - 1, j - t)$。

直接做是 $O(nk^2)$ 的,可以使用前缀和优化到 $O(nk)$。

N Slimes

不会吧,不会吧,不会真的有人没做过石子合并吧?

设 $f(i, j)$ 为合并 $[i, j]$ 所需的最小代价,$s(l, r) = \sum \limits_{i = l}^r a_i$,那么有 $f(i, j) = \min \limits_{k = l}^{r - 1} \{f(i, k) + f(k + 1, j) + s(i, j)\}$。时间复杂度 $O(n^3)$。

可以用四边形不等式优化到 $O(n^2)$,用 GarsiaWachs 算法做到 $O(n \log n)$。

O Matching

考虑状压 DP,设 $f(i, S)$ 为 $A$ 中 $i$ 个人跟 $S$ 匹配的方案数,如果要转移的话,那么必须满足 $S$ 中 $1$ 的数量等于 $i$(满足两两匹配)。

考虑转移:我们找到一个 $j$,使得 $i$ 到 $j$ 有边并且 $j$ 当前没有匹配过,更新 $f(i + 1, S \cup \{j\})$,这样就找到了一组新的匹配。时间复杂度 $O(n \cdot 2^n)$。

P Independent Set

设 $f(i, 0/1)$ 为节点 $i$ 染黑色 / 白色的方案数。设 $j \in \operatorname{Subtree}(i)$,那么有

$$f(i, 0) = \prod (f(j, 1))$$

$$f(i, 1) = \prod (f(j, 0) + f(j, 1))$$

答案为 $f(i, 0) + f(i, 1)$。

Q Flowers

设 $f(i)$ 表示以 $i$ 结尾的最大收益,那么答案即为 $\max \limits_{i = 1}^n f(i)$。考虑怎么维护 $f(i)$,这个其实很好想,就是 $f(i) = \max\limits_{j < i \land h_j < h_i} f(j) + a_i$。直接做是 $O(n^2)$ 的。

注意到可以用线段树维护最大值做到 $O(n \log n)$。

R Walk

矩阵优化图上问题的模板。直接给出结论:将邻接矩阵做 $k$ 次乘法后,$g^k_{i, j}$ 表示从 $i$ 到 $j$,经过 $k$ 条边的方案数。答案即为 $\sum \limits_{i = 1}^n \sum \limits_{j = 1}^n g^k_{i, j}$。

S Digit Sum

数位 DP 的模板题。设 $f(i, s, 0/1)$ 表示枚举到第 $i$ 位,和在模 $D$ 意义下为 $s$,是否顶上限的方案数,然后大力记忆化搜索即可。由于题目直接给了数位形式,所以我的代码是从 $1$ 枚举到第 $n$ 位的。

数位 DP 居然 WA 了一次,丢人了(

不过 NOIp 从来没考过数位 DP?(

Last modification:September 2nd, 2021 at 02:15 am