Atcoder dp edu contest

记得写一下多重，树上，分组背包。

关于 dp 的一些注意事项ψ(｀∇´)ψ

状态设计

只需要考虑把题目中的要素（信息）添加进去，状态合法性啥的在推方程的时候再作检查和修改。

首先是阶段，不同类型的 dp 通常都有常见的”阶段“。

比如线性 dp 就是考虑前 $i$，树型 dp 就是考虑以 $u$ 为根的子树。

然后再把决策对应的信息添加进去，比如第 $i$ 个位置是选还是不选，第 $i$ 个位置选了 $j$ 这种信息。

状态转移方程

一般用决策 + 状态定义的方法推方程，就是考虑这一步决策对 $dp$ 造成的影响，它上一步可以从什么地方转移过来，一般是上一个位置（$i - 1$ 或者是用变量枚举），父亲节点（树型 dp 常见），

或者直接用集合思维也行（$dp$ 数组表示可行方案集合，并且带有属性，利用决策和上一步（最后一个不同元素）划分集合），反正怎么好怎么来。

此时要先检查状态以及转移方程的合法性，也就是利用集合思维确定是否覆盖了整个状态空间（是否漏掉了状态），并检查后效性（转移是否成环）。

如果是计数类 dp 还需要考虑是否会算重（检查是否会把某一个状态/决策计算多次）。

如果合法性，后效性，不重不漏性没有得到保证，通常的解决方案就是考虑在 dp 数组里添加维度记录额外的信息，或者是更改状态和转移方式，甚至是利用辅助数组记录信息。

后效性的解决还可以考虑高斯消元或者更改枚举顺序，不重复性的保证可以考虑容斥原理，不漏性/合法性可以考虑 Exchange Argument 等（比如 Code Festival 2017 的 Zabuton）。

初始化

初始化按照定义来即可，一般用 $+-\infty$ 表示不合法，方案数和概率 DP 一般用 $0$，目标状态也是根据定义来就行了。

优化方程和状态

一定要先推出最暴力的方程然后再考虑优化，不然容易思维固化想不到优化过的思路，当然如果有巧妙的转化能直接想到优秀的状态也行。

常见的优化空间的方式就是滚动数组，还有对状态本身进行优化（比如如果可以用阶段+一个决策推出另外一个决策，另外一个决策就不用记录了，比如 Mobile Service）。

常见的优化时间的方式就是前缀和优化，单调队列，数据结构，斜率优化这些对于特殊的转移方程中的决策集合选取的优化（比如多重背包，Optimal Partition 这种），有的时候还有利用可行性的约束来优化的（比如那个状态只会在长度为 $256$ 的区间内转移的 CF 题 Xor-Subsequence）。

题目ψ(｀∇´)ψ

题面

C - Vacationψ(｀∇´)ψ

设 $dp(i, 0/1/2)$ 表示这个人第 $i$ 天选择了 $0/1/2$ 活动，获得的最大值。

然后限制条件是相邻的不能选一样的活动。

所以就是个状态机 DP。

$dp(i, 0) = \max\{dp(i-1,1) + w0_i, dp(i - 1,2) + w0_i\}$。

然后另外两种完全一样。

思考一下发现，如果这一天选了 $0$，只需要关心 $i - 1$ 这一天的，一共也只有选 $1/2$ 的可能，所以状态空间肯定覆盖满了，合理。

E - Knapsack2ψ(｀∇´)ψ

$m \le 10^9$ 的 01 背包问题，体积都变成 $10^9$，但是价值变成 $10^3$ 了。

可以考虑离散化，但是这是负作用，因为实际会有 $2^n$ 级别的数需要离散化。

注意到 $n$ 只有 $100$，所以能取得的总价值一定不超过 $10^5$。

那么可以考虑交换一下维度，设 $dp(i)$ 表示取到 $i$ 的价值最少要多少空间。

然后类似背包更新，最后在可行状态里面找最大的 $i$ 即可。

很 Educational 的一个题。

G - Longest Pathψ(｀∇´)ψ

板子题，不讨论。

I - Coinsψ(｀∇´)ψ

设 $dp(i, j)$ 表示考虑前 $i$，有 $j$ 个正（其他 $i - j$ 个就是反）的概率。

考虑转移，显然决策是对于 $i$ 考虑正反，每次 $j$ 的变化最多 $1$，我们只需要考虑从上一个转移过来即可。

由乘法原理和加法原理，显然有：

$dp(i,j) = dp(i-1,j) \times(1-p_i) + dp(i -1,j - 1)\times p_i$。

（不管前面的方案是由多少种方案凑的，因为在这一步都直接乘了同一个数所以可以结合律，那么这个状态表示就显然是对的，也可利用集合思想考虑）

然后做完了。

M - Candiesψ(｀∇´)ψ

考虑设 $dp(i, j)$ 表示考虑前 $i$ 个人，第 $i$ 个人拿了 $j$ 个的方案数，显然无法得知之前用过多少个，题目要求有恰好用完，所以寄掉了。

以此为出发点，改进状态，设 $dp(i,j)$ 为第 $i$ 个人，当前一共使用了 $j\in[0,K]$ 个的方案数。

然后每个人拿的个数限制是 $[0,a_i]$，所以考虑 $O(nK^2)$ 枚举，转移是： $$ dp(i,j) = \sum\limits_{k = 0}^{\min(a_i, j)} dp(i - 1, j - k) $$ 思考一下合法性和不重复性，感觉显然不会有重复！

但是发现这个转移有点铸币，$K$ 是 $10^5$ 的，没法做，但是类似 Problem T，这是一个上一阶段前缀和的形式，可以考虑前缀和优化，复杂度 $O(nK)$ 应该可以过了。

答案是直接选 $dp(n, K)$，初始化 $dp(i,0) = 1, i \in[0, n]$，其余为 $0$。

O - Matchingψ(｀∇´)ψ

二分图完美匹配计数，$n \le 21$。

明显可以状压 dp，设 $dp(msk)$ 表示左部点的匹配状态为 $msk$ 的方案数，发现没法记录右部点的状态，无法得知当前算的这一个之前是不是已经被用掉了。

然后如果两边都用 $msk$ 状压，空间复杂度 $O(2^{42})$，寄掉了，所以考虑把左部点作为阶段，对于每个左部点考虑计数。

那么状态就是 $dp(i, msk)$ 表示左部点匹配了前 $i$，右部点匹配状态为 $msk$ 的方案，最终答案为 $dp(n, 2^{msk} - 1)$。

状态转移可以设计为 $dp(i - 1, msk^\prime) \to dp(i, msk)$，其中 $msk^\prime$ 是扣掉一个 $msk$ 中能够和 $i$ 匹配的节点形成的原始状态（所以这里是可以预处理优化的）。

这里状态都会从上一层转移过来，然后决策也没有漏掉什么或者多次决策一个，所以状态是可行的。

然后发现 $\text{popcnt}(msk) \not= i$ 的状态肯定不合法，所以还可以直接 continue 或者预处理搞掉。

复杂度 $O(n^22^n)$。

然后这破玩意儿实际上可以直接优化掉，但是我懒，所以不。

P - Independent Setψ(｀∇´)ψ

考虑设 $dp(u, 0/1)$ 表示考虑 $u$ 这个节点，涂成黑色/白色的方案数。

然后题目要求不能够有两个相邻的黑色，所以分类讨论写出转移：

\[ \begin{cases} dp(u,0) =\prod\limits_{v \in \text{son}(u)} dp(v,1) \\ dp(v, 1) = \prod\limits_{v\in \text{son(u)}} [dp(v,0) + dp(v,1)] \end{cases} \]

注意到 $dp(v,1)$ 的那个柿子不能是直接 $dp(v,0) \times dp(v,1)$，显然方案数不对，稍微用一下加法原理或者画出来合并一下就能推出这个柿子。

然后有一个注意的点就是乘法可能在过程中就爆掉了，不然直接 i64 定义 dp，不然就多取模，记得初始化为 $1$。

Q - Flowersψ(｀∇´)ψ

考虑设 $dp(i)$ 表示以 $i$ 结尾的子序列中， $a_i$ 上升，$\sum b_i$ 的最大值。

然后考虑转移，枚举上一个位置即可：

\[ dp(i) = \max\limits_{j = 1}^{i - 1} \{dp(j) + b_i (\text{if}\ a_i > a_j).\} \]

但是这个方程有没有问题？先考虑一下合法性。

有没有一种可能就是，我前面选了一堆，然后选了 $i$，但是选了 $i$ 之后后面一个更大的 $j$ 没法选了？

显然不可能吧！这就是在用贪心的思想思考 dp了，显然不对！$j$ 这个位置的 $dp(j)$ 肯定会枚举前面的所有可行状态来更新的。

因为状态强制选 $i$，所以我们只需要考虑 $a_i$ 和 $a_j$ 的大小关系就行了，不需要再考虑 $dp(i)$ 状态中 $i$ 前面的决策！

所以合法性肯定有保证，状态空间也覆盖满了。

但是现在这个方程是 $O(n^2)$ 的，$2e5$ 过不了，但是看到这个方程是在 $dp$ 的某一个前缀当中取 $\max$，要求复杂度 $\log$ 级别。

而且转移有关键码 $a_i$ 的大小要求（关键码还互不相同），决策的收获 $b_i$ 还是可以从 $\max$ 里面拆出来的。

所以类似 Optimal Partition 那题，我们考虑值域树状数组优化 dp，先对 $a_i$ 离散化，然后按照顺序一个一个插入更新完了的 $dp(i)$，每次转移直接在树状数组上询问前缀 $\max$ 即可（本题 $a_i$ 已经自动离散化过了，不需要额外离散化）。

（实际上就是在询问，满足 $j < i, a_j < a_i$ 的最大的 $dp(j)$ 是多少，用它转移过来即可）

最后给所有 $dp$ 取一个 max 即可，其实 $dp$ 数组都可以不要了，直接在树状数组上修改转移就行。

R - Walkψ(｀∇´)ψ

求恰好 $K$ 条边的路径数量，考虑类似恰好 $K$ 条边最短路，利用邻接矩阵的另外一种定义 + 计数时运算存在的结合律转化成矩阵快速幂。

如果 $A_r$ 表示恰好 $r$ 条边的路径数量矩阵，那么 $A_r[i,j] = \sum\limits_{k = 1}^n (A_{r - 1}[i, k] \times A_1[k,j])$。

注意取模，然后矩阵快速幂即可 $O(n^3\log K)$ 求出答案。

S - Dight Sumψ(｀∇´)ψ

简单的数位 DP，我们考虑抽象出所有要求直接上记忆化搜索的板子。

然后发现也没啥可以抽象的，就只有数字十进制下的数位和是 $D$ 的倍数的这一个要求。

但是注意到这里不会在填数的时候排除任何决策，因为决策的合法性要到最后才能判定，所以记得把边界答案分情况。

T - Permutationψ(｀∇´)ψ

设 $dp(i,j)$ 表示考虑前 $i$，第 $i$ 个选了 $j$ 的方案数。

然后发现很烦啊！没法知道前面是否选过 $j$，显然状态本身合法性得不到保证！

然后有一个思路就是我给 $dp$ 附加一些信息，比如设 $dp(i,j)$ 表示考虑前 $i$ 个位置选 $1\sim i$ 的排列，第 $i$ 个选了 $j$ 的方案数。

发现还是没法覆盖完问题的状态空间，比如 $1,3,5,2\ |\ 4$ 这种情况（$4$ 是当前的决策），很显然找不到任何一个状态去表示前面的 $1,3,5,2$ 啊。

于是我们考虑更改一下状态本身，我们设 $dp(i,j)$ 表示前 $i$ 个数，第 $i$ 个数的排名在已经选择的前 $i$ 个数当中为 $j$ 的方案数，这样就能表示前面的状态了。

分情况讨论可以得到：

如果 $s_i = \texttt{<}$ ，那么 $i - 1$ 的 rank 肯定小于 $i$ 的 rank，可以得到转移为 $dp(i,j) = \sum\limits_{k = 1}^{j-1} dp(i - 1, k)$。

反之，$dp(i,j) = \sum\limits_{k = j}^i dp(i - 1, k)$，注意此时加入 $i$ 之后 $i - 1$ 的 rank 会上升，所以 $k$ 要从 $j$ 开始枚举。

发现要枚举 $i,j,k$，复杂度 $O(n^3)$，过不了，但是这个 $\sum$ 是上一层状态的连续的一段，可以直接前缀和优化决策以及转移。

然后复杂度就是 $O(n^2)$ 了，也很 Educational。

V - Subtreeψ(｀∇´)ψ

绝对很 Educational 的换根 dp，类似 P 题，我们设 $dp(u, 0/1)$ 表示，在以 $1$ 为根的前提下，$u$ 取黑/白，在以 $u$ 为根的子树中的方案数。

发现本题要求所有黑点必须处于同一个连通块，所以 $dp(u, 1)$ 实际上全部都是 $1$。

那么可以写出转移方程：

\[ dp(u) = \prod\limits_{v \in \text{son}(u)} (dp(v) + 1) \]

这是以 $1$ 为根的情况，我们设 $ndp(u)$ 表示整棵树以 $u$ 为根的时候的总方案数。

考虑换根，发现对于一个节点 $v$，如果它的父亲节点（以 $1$ 为根时）是 $u$，那么以 $v$ 为整棵树的树根的时候，答案应当从 $u$ 和 $\text{son} (v)$ 中转移过来。

因为 $ndp(u)$ 用到了 $dp(v)$ 来转移（实际上是 $dp(u)$ 用了 $dp(v)$ 然后 $ndp(u)$ 用了 $dp(u)$），所以我们要把 $dp(v)$ 的贡献从 $ndp(u)$ 当中扣掉，转移方程是：

\[ ndp(v) =dp(v) \times (\dfrac{ndp(u)}{dp(v) + 1} + 1) \]

但是发现本题取模并不是质数，不一定存在逆元，也就是不能直接在转移的时候乘上 $\text{inv}(dp(v) + 1)$。

我们尝试改写一下这个式子：

\[ \begin{aligned} ndp(v) &= dp(v) + dp(v)\times\dfrac{ndp(u)}{dp(v) + 1}\\ ndp(v) &= dp(v) + ndp(u) \times \dfrac{dp(v)}{dp(v) + 1}\\ \end{aligned} \]

发现这个乘上的 $dp(v)$ 有点烦（作为加法项存在，在一个做乘法的式子里不好直接拆开），我们拿掉它，也就是令 $nndp(v) \times dp(v)= ndp(v)$。

然后我们考虑计算 $nndp(v)$，最后计算答案的时候乘上 $dp(v)$ 即可。

写出来：

\[ \begin{aligned} nndp(v) &= \dfrac{ndp(u)}{dp(v) + 1} + 1\\ nndp(v) &= nndp(u) \times \dfrac{dp(u)}{dp(v) + 1} + 1\\ nndp(v) &= [nndp(u) \times \prod\limits_{x \in \text{son}(u)\land x \not= v} (dp(x) + 1) ] + 1 \end{aligned} \]

所以我们只需要在转移之前对于每个节点维护一下它的儿子节点的贡献的前后缀积即可，为了方便处理使用 vector 存边。

W - Intervalψ(｀∇´)ψ

先给区间排个序。

设 $dp(i，0/1)$ 表示考虑前 $i$ 个，第 $i$ 个选还是不选的最大值。

如果选就枚举上一个位置然后取 max，如果不选就在前面所有状态取 max。

\[ dp(i, 0) = \max\limits_{j = 1}^{i -1}\{dp(j, 0), dp(j, 1)\} \]

\[ dp(i,1) = \max\limits_{j = 1}^{i-1}\{dp(j, 0), dp(j,1)\} + w_i \]

考虑一下是否覆盖了完整的状态空间，合法性有没有保障。

注意到区间之间有包含和覆盖关系，可能会出现被强制选上的情况，看看这个状态是否可以处理。

直接嗯看有点难顶，观察一下题目样例：

很显然是有问题的，就上面这个样例，$dp(2/3/4,0)$ 的转移显然都不合法了。

所以现在要做的就是在转移的时候保证转移的合法性。

显然选区间的位置会影响到之后的转移，我们考虑记录这个位置，状态变为 $dp(i,j)$ 表示前 $i$ 个，考虑第 $i$ 个区间选了 $j$ 这个位置的最大值，如果 $j = 0$ 代表不选这个区间，其他 $j\not\in [l_i,r_i]$ 的状态全部置为 $-\infty$。

然后状态转移方程就变成这样了：

\[ \begin{aligned} dp(i,0) &= \max\limits_{j = 1}^{i - 1}\{dp(i, k)(\text{if } k<l_i), dp(j, 0)\}\\ dp(i,x) &= \max\limits_{j = 1}^{i - 1}\{dp(j, k) + w_i, dp(j, 0) + w_i (\text{if } x\not\in [l_j,r_j])\} \end{aligned} \]

这个最多也就能优化到 $n^2\log$ ，寄掉了。

现在还不会。

X - Towersψ(｀∇´)ψ

题解咕咕掉了。

Y - Grid2ψ(｀∇´)ψ

不会。

Z - Frog3ψ(｀∇´)ψ

不会。

最后更新: September 14, 2023

Atcoder dp edu contest

关于 dp 的一些注意事项ψ(｀∇´)ψ

题目ψ(｀∇´)ψ

A - Frog1ψ(｀∇´)ψ

B - Frog2ψ(｀∇´)ψ

C - Vacationψ(｀∇´)ψ

D - Knapsack1ψ(｀∇´)ψ