当前位置：首页 > news >正文

AtCoder DP Educational Contest

news 2026/5/12 12:53:21

将类似 AtCoder-dp_c 的题暂且称为「多状态序列 DP」？

「前驱状态」就是，当前状态从哪些状态递推过来，i.e., the statuses from which the current status is obtained。

设 $\mathrm{exp}$ 为一个逻辑表达式，Iverson 记号 $[\mathrm{exp}]$ 定义为：$[\mathrm{exp}]=1$ 若 $\mathrm{exp}$ 为真；$[\mathrm{exp}]=0$ 若 $\mathrm{exp}$ 为假。

以 $u$ 为根的子树，下面简称「$u$ 子树」。

作为经典 DP 问题的复习？

A：基础序列 DP。$dp(i)=\min\{dp(i-1)+|h_i-h_{i-1}|,dp(i-2)+|h_i-h_{i-2}|\}$。
B：上一题的略微扩展。$dp(i)=\min_{k=1}^K[dp(i-k)+|h_i-h_{i-k}|]$。$K\le100$，暴力即可。
C：基础多状态序列 DP。$dp(i,k)$ 表示前 $i$ 天，第 $i$ 天做了活动 $k$（$k\in\{0,1,2\}$）。$dp(i,k)=\max_{j\ne k}[dp(i-1,j)]+A_{k,i}$。
D：经典 0/1 背包。$dp(i,j)=\max\{dp(i-1,j),dp(i-1,j-w_i)+v_i\}$。
E：0/1 背包，但注意数据范围的变化：容量 $W\le10^9$，但价值 $v_i\le10^3$。设 $dp(i,j)$ 表示用前 $i$ 个物品，凑成总价值为 $j$，所需的最小重量。那么有 $dp(i,j)=\min\{dp(i-1,j),dp(i-1,j-v_i)+w_i\}$。初值为 $+\infty$（除了 $dp(0,0)=0$）。答案为使得 $dp(N,j)\le W$ 的最大的 $j$。时间 $O(N^2V)$，其中 $V=\max\{v_i\}$。
F：经典 LCS 问题。$dp(i,j)=\max\{dp(i-1,j),dp(i,j-1),dp(i-1,j-1)\cdot[s_i=t_j]\}$。
G：经典 DAG 最长路问题。按拓扑序 DP，若有边 $u\to v$，则进行转移 $dp(v)\xleftarrow{\max}\{dp(u)+1\}$。
H：基础，网格上的多维线性 DP。$dp(i,j)=[a_{i,j}=\texttt.]\cdot[dp(i-1,j)+dp(i,j-1)]$。初值 $dp(1,1)=1$。
I：设 $dp(i,j)$ 表示前 $i$ 个硬币中出现 $j$ 个正面的概率，则 $dp(i,j)=p_i\cdot dp(i-1,j-1)+(1-p_i)\cdot dp(i-1,j)$。初值 $dp(0,0)=1$。
*J：期望 DP。套路地，由于目标状态是确定的，设 DP 值为 到达目标状态 的期望步数。

设 $dp(i,j,k)$ 表示分别有 $i,j,k$ 个盘子中有 $1,2,3$ 个寿司（同时 $N-i-j-k$ 个盘子中没有寿司）时，要吃完所有寿司 的期望操作次数。那么讨论当前对哪种盘子进行吃寿司的操作，前驱状态为吃完当前寿司后的状态，得到状态转移方程

\[\begin{aligned} dp(i,j,k)&=\frac iN[dp(i-1,j,k)+1]+\frac jN[dp(i,j+1,k-1)+1]\\ &+\frac kN[dp(i+1,j-1,k)+1]+\frac{N-i-j-k}N[dp(i,j,k)+1]. \end{aligned} \]
移项化简一下，得到

\[dp(i,j,k)=\frac{i\cdot dp(i-1,j,k)+j\cdot dp(i,j+1,k-1)+k\cdot dp(i+1,j-1,k)+N}{i+j+k}. \]
注意如何满足 无后效性：由于 $k$ 递增，以 $k$ 为最外层；在与当前状态 $k$ 相同的前驱状态中，$j$ 又是递增的，以 $j$ 为第二层；$j$ 相同，$i$ 递增，以 $i$ 为第三层。
K：集合 Nim。设 $dp(i)$ 表示剩余 $i$ 块石头是否是必胜态。初值 $dp(0)=\mathrm{false}$ 为必败态。只要下一步存在一个必败态，那么当前就是必胜态。因此有 $dp(i)=\bigvee_{i=1}^N\lnot dp(i-a_i)$，$\vee$ 表示逻辑或，$\lnot$ 表示逻辑非。

事实上求 SG 值也可以，即 $dp(i)=\operatorname{mex}_{i=1}^Ndp(i-a_i)$，如果 $dp(K)=0$ 则必败，否则必胜。
*L：区间 DP，但不是合并，而是扩张。由于目标状态是确定的（全部取完），设 DP 值表示从当前状态开始全部取完后的最优值。

设 $dp(i,j)$ 表示 剩下的 区间为 $[i,j]$ 时，$X-Y$ 可以达到的最优值。这样，我们同时知道已经取走了 $c=N-(j-i+1)$ 个数，也就知道现在应该谁来取，进而知道当前应该最大化还是最小化。前驱状态为当前取完的状态，故有

\[dp(i,j)=\begin{cases}\max\{dp(i+1,j)+a_i,dp(i,j-1)+a_j\},&\text{$c$ is even},\\\min\{dp(i+1,j)+a_i,dp(i,j-1)+a_j\},&\text{$c$ is odd}.\end{cases} \]
初值 $dp(i+1,i)=0$，答案 $dp(1,N)$。时间 $O(N^2)$。
M：设 $dp(i,j)$ 表示前 $i$ 个孩子共分到 $j$ 颗糖果的方案数。则 $dp(i,j)=\sum_{k=1}^{\min\{j,a_i\}}dp(i-1,j-k)$。前缀和优化即可。
N：合并类区间 DP 模板题（石子合并）。$dp(i,j)=\min_{i\le k<j}[dp(i,k)+dp(k+1,j)]+\sum_{p=i}^ja_p$。
O：$N\le21$，状态压缩 DP。设 $dp(i,S)$ 为前 $i$ 个男性和集合 $S$ 中的女性构成匹配的方案数，其中集合 $S$ 在代码中用一个长度为 $N$ 的二进制数表示。状态转移：$dp(i,S)=\sum_{j=1}^Na_{i,j}\cdot[j\in S]\cdot dp(i-1,S\setminus\{j\})$。注意必须有 $|S|=i$，因此可以不必枚举 $i$。时间 $O(N\cdot2^N)$。
P：树形 DP 模板题。设 $dp(u,0/1)$ 表示 $u$ 子树已染色，且 $u$ 被染成白色 / 黑色的方案数。设 $v$ 为 $u$ 的子节点，则有

\[dp(u,0)=\prod_v[dp(v,0)+dp(v,1)],\quad dp(u,1)=\prod_vdp(v,0). \]
初值为 $dp(l,0)=dp(l,1)=1$，其中 $l$ 为任一叶子。答案为 $dp(u,0)+dp(u,1)$。
Q：类似 LIS 的序列 DP。设 $dp(i)$ 表示以 $i$ 为结尾、且满足高度严格上升的子序列中，美丽值之和的最大值。那么有 $dp(i)=\max\limits_{1\le j<i,h_j<h_i}dp(j)+a_i$。$N\le2\cdot10^5$，需要优化，用权值树状数组动态维护前缀 max。时间 $O(N\log N)$。
R：邻接矩阵的应用。设 $A$ 为图的邻接矩阵，则答案为 $\sum_{1\le i,j\le N}A^k_{i,j}$。使用矩阵快速幂，$O(N^3\log K)$。
S：数位 DP。先咕了。
*T：设 $dp(i,j)$ 表示用 $1,\cdots,i$ 填前 $i$ 位，且第 $i$ 位为 $j$ 的方案数。一个 trick：为了保证构成排列，即当前填的 $j$ 与之前填的数不重复，可以将之前填的数中 $\ge j$ 的所有数全部 $+1$，然后再 append 一个 $i$。这样就保证了构成 $(i,j)$ 这一状态，并且转移显然只与 $i,j$ 有关。状态转移方程：

\[dp(i,j)=\begin{cases}\sum_{k=1}^{j-1}dp(i-1,k),&s_{i-1}=\texttt<,\\\sum_{k=j}^{i-1}dp(i-1,k),&s_{i-1}=\texttt>.\end{cases} \]
使用前缀和优化，时间复杂度 $O(N^2)$。
U：枚举子集 的状态压缩 DP。设 $dp(S)$ 为使用集合 $S$ 中的兔子得到的最大答案，其中 $S\subseteq\{1,\cdots,N\}$。再枚举 $S$ 的子集 $T$ 作为分到新的一组的兔子，得到状态转移方程：

\[dp(S)=\max_{T\subseteq S}\left[dp(S\setminus T)+\sum_{x,y\in T,x<y}a_{x,y}\right]. \]
后面的一项这可以 $O(N^2\cdot2^N)$ 预处理。瓶颈在于，枚举 $S$ 再不重不漏地枚举 $S$ 的子集，暴力是 $O(2^{2N})$ 的（虽然远远卡不满）。事实上，枚举子集可以用如下代码实现：
```
for (int t = s; t; t = (t - 1) & s) { // s 为集合 (二进制数), t 为 s 的所有子集// ...
}
```
枚举子集的复杂度：

\[\sum_{S\subseteq\{1,\cdots,N\}}2^{|S|}=\sum_{i=0}^{N}\binom Ni\cdot2^i=\sum_{i=0}^N\binom Ni\cdot2^i\cdot1^{N-i}=(2+1)^N=3^N. \]
故总时间复杂度为 $O(N^2\cdot2^N+3^N)$。
V：换根 DP。先固定根，设 $f(u)$ 为将 $u$ 子树染色，且 $u$ 为黑色的方案数，则 $f(u)=\prod_v[f(v)+1]$，其中 $v$ 为 $u$ 的儿子。

再考虑换根，设 $g(u)$ 为将 $u$ 染成黑色的方案数（也就是答案）。求从 $g(u)$ 到 $g(v)$ 的递推关系，其中 $u$ 是 $v$ 的父亲。$v$ 对 $u$ 的贡献是 $f(v)+1$，因此 $g(u)$ 中除了 $v$ 子树的部分的染色方案数为 $\dfrac{g(u)}{f(v)+1}$，故 $g(v)=f(v)\cdot\left[\dfrac{g(u)}{f(v)+1}+1\right]$。

然而，模数 $M$ 不一定是质数，可能不存在逆元，因此需要避免除法。设 $u$ 的儿子为 $v_1,\cdots,v_k$，前缀积 $pre(v_i)=\prod_{j=1}^i[f(v_j)+1]$，后缀积 $suf(v_i)=\prod_{j=i}^k[f(v_j)+1]$。重新设 $g(u)$ 表示对除了 $u$ 子树的部分染色，且 $u$ 染成黑色的方案数，则

\[g(v_i)=g(u)\cdot pre(v_{i-1})\cdot suf(v_{i+1})+1, \]
进而答案为 $ans(v)=f(v)\cdot g(v)$。
*W：设 $dp(i)$ 表示考虑前 $i$ 位（的所有完整区间），且第 $i$ 位为 $1$ 的答案。转移的不同决策来自于 最后一段连续 $0$ 的长度 不同，令 $[j,i-1]$ 为最后一段极长连续 $0$，则 $dp(i)=\max_{j=1}^i[dp(j-1)+\sum_{j\le l_k\le i\le r_k}a_k]$。

考虑如何用数据结构优化。用线段树维护 $val(j)=dp(j-1)+\sum_{j\le l_k\le i\le r_k}a_k$，随着 $i$ 向右扫描，产生贡献的 $a_k$ 会减少，在线段树上进行区间修改即可。具体来说，就是：
1. 对所有 $l_k=i$ 的 $k$，令所有 $j\in[1,l_k]$ 的 $val(j)$ 加上 $a_k$；
2. 查询 $dp(i)=\max_{j=1}^ival(j)$；
3. 令 $val(i+1)$ 加上 $dp(i)$；
4. 对所有 $r_k=i$ 的 $k$，令所有 $j\in[1,l_k]$ 的 $val(j)$ 减去 $a_k$，即将该区间的贡献撤销。
设 $dp(0)=0$，答案为 $\max_{i=0}^Ndp(i)$。
X：贪心优化 DP。假设已经决定好了要拿哪些箱子，那么这些箱子要按照 $w_i+s_i$ 上升的顺序从上到下排列（洛谷-P1842 奶牛玩杂技）。因此先排序，然后就是 0/1 背包模板题了（不过转移时要保证，当前塔的承重可以作为塔底）。
Y：CodeForces-559C Gerald and Giant Chess。考虑容斥，用总路径数减去经过墙的路径数。设 $dp(i)$ 表示从 $(1,1)$ 到墙 $(r_i,c_i)$，且中途不经过其他墙的路径数。转移时，讨论从 $(1,1)$ 到墙 $i$ 经过的第一个墙 $j$，则有

\[dp(i)=\binom{r_i-1+c_i-1}{r_i-1}-\sum_{j=1}^{i-1}[r_j\le r_i\land c_j\le c_i]\cdot dp(j)\cdot\binom{r_i-r_j+c_i-c_j}{r_i-r_j}. \]
设 $(r_{n+1},c_{n+1})=(H,W)$，答案为 $dp(n+1)$。
Z：斜率优化 DP。设 $dp(i)$，则有

\[dp(i)=\min_{j=1}^{i-1}[dp(j)+(h_j-h_i)^2+C]=\min_{j=1}^{i-1}[dp(j)+h_j^2-2h_i\cdot h_j]+h_i^2+C. \]
todo.