dp 题单
Diu 的 dp 题单
原本想写学习笔记的，但是 dp 题目太多，套路太深，我把握不住，所以我决定改成写题单。
本题单主要收录一些 dp 题目的神秘操作，当然也有一些套路比较常见，只是选一些做代表收录。
CF1626 A Random Code Problem
期望 dp，桶：开一个桶维护 \(f_{i,j}\) 表示操作 \(i\) 次之后共有多少个 \(j\)，对于每一个 dp 值统计答案，设 \(L=\gcd(1,2,\dots,k-1)\)，发现 \(L\lfloor\frac{a_i}{L}\rfloor\) 的部分始终不变，统一统计即可。
P3736 [HAOI2016]字符合并
区间 dp 和状压 dp：设 \(f_{i,j,s}\) 表示区间 \([i,j]\) 的串最后合并成串 \(s\) 的最大分数。发现因为每次合并的价值均为正数，所以能合并肯定合并，所以最后一个固定的区间 \([i,j]\) 会合并成长度为 \((j-i-1)\%(k-1)+1\) 的串，直接暴力 dp 即可。
P4007 小 Y 和恐怖的奴隶主
矩阵优化，卡常：发现 \(m\) 很小，但是 \(n\) 很大，考虑直接开 \(m\) 维维护血量。设 \(f_{i,a,b,c}\) 表示攻击 \(i\) 次，有 \(a\) 个奴隶主血量为 \(1\)，\(b\) 个奴隶主血量为 \(2\)，\(c\) 个奴隶主血量为 \(3\) 的期望打掉 boss 的血量，直接从 \(f_i\) 暴力构建转移矩阵到 \(f_{i+1}\)，复杂度 \(O(T166^3\log n)\)。多组数据时，一个优化是把 \(2\) 的次幂的矩阵预处理出来，然后每次二进制拆分，用一个行矩阵（或列矩阵）乘上需要的，优化到 \(O(166^3+T166^2\log n)\)。还需卡常，在矩乘时用一个 __int128 做中间量，最后统一取模。
P4590 [TJOI2018]游园会
状压，dp 套 dp：字符串计数，考虑 \(f_{i,\dots}\) 表示前 \(i\) 个字符，满足什么状态的方案数。对于 \(NOI\) 的限制，我们可以考虑加一位 \(0/1/2\) 表示和 \(NOI\) 的匹配程度。对于最长公共子序列，我们可以考虑还原在 dp 求最长公共子序列的过程。如果把兑奖串看做已知，那么设 \(dp_{i,j}\) 表示第一个串前 \(i\) 个字符，第二个串的前 \(j\) 个字符匹配了多少个，那么 \(dp_{i,j}=\max(dp_{i,j-1},dp_{i-1,j},dp_{i-1,j-1}+[s_i=s_j])\)。发现 \(dp_i\) 的转移只和 \(dp_{i-1}\) 有关。我们可以考虑用一个状态 \(s\) 存储一个 \(dp_i\)，然后每次转移暴力解压出来，更新完之后再压缩回去。但是这样做状态数很多，我们可以发现 \(dp_{i,j}-dp_{i,j-1}=0/1\)，所以我们可以把 \(dp_i\) 差分起来，再状压。
CF1648C Tyler and Strings
计数 dp，数据结构优化：我们从小到大枚举每一位 \(i\) 表示 \(s\) 和 \(t\) 前 \(i\) 位相同的情况，更新桶，表示当前可用点。如果第 \(i+1\) 位使得 \(s\) 字典序更小，那么后面的可以乱填。那么假设 \(c_i\) 是桶，对于一个 \(j
SOJ 4. Journey
期望树形 dp，容斥，卡常
SOJ 5. Festival
期望计数 dp
SOJ 6. Random
期望 dp，矩阵优化，cdq
以上三题做法太神仙，笔者太弱，无法很好总结，另见 solution。
SOJ 1.博弈
博弈论，DAG 图上 dp，背包 dp：可以发现每个点有无棋子对答案贡献互相独立，可以用一次 dp 解决。可以先设 \(f_v\) 表示节点 \(u\) 可以使得当前先手领先多少个点，对于一个可以转移的 \(v\)，如果 \(u,v\) 同色，那么 \(f_u\Leftarrow f_v+1\)，否则 \(f_u\Leftarrow -f_v+1\)，\(f_u\) 在所有状态中取 \(\max\)，特殊地，持棋者可以一步不走，所以 \(f_u\) 也可以为 \(0\)。一遍 dp 更新完 \(f\) 之后，我们按颜色分开，即一部分是对 A 有正贡献，一部分是负贡献。那么对两者分别跑背包，然后统计即可。
P6803 [CEOI2020]星际迷航
博弈论，树形 dp，矩阵优化：模拟赛时奇妙 65 分，至今不知原因。
我们发现除了第一棵树，其他树上节点我们只需要知道以它为根节点的情况，可以考虑换根 dp。我们发现一个一个必胜点向后面接了一条边什么事都无，而一个必败点往后借一条边，如果连的是必胜也无用，否则会改变某一些点的 dp 值。我们可以考虑矩阵优化。最后再做一次树形 dp 统计答案即可，细节极多。
CF1500F Cupboards Jumps
构造，普通 dp，set 的神秘操作：我们发现题目和 \(h\) 的值无关，只和 \(h\) 的差分有关，所以我们考虑对差分 \(d_i\) 进行 dp，直接设 \(f_{i,x}\) 表示前 \(i\) 个数中 \(|d_i|=x\) 是否可行。然后我们可以发现 dp 数组的转移情况只有：以某个点为中心翻转，整个值域覆盖，删除或加入单点。我们发现单点的值不多，可以用 set 维护，对于区间翻转操作，可以用两个便捷维护，用两个值维护区间是否翻转，即区间便宜的值。每次翻转操作我们对整个区间进行翻转，这样单次复杂度 \(O(\log n)\)。
P6773 [NOI2020] 命运
计数树形 dp，线段树合并维护：因为所给的链都是返祖链（两个端点有祖先-后代关系的链），所以我们可以设 \(f_{u,i}\) 表示子树 \(u\) 内，需要在深度为 \(i\) 的祖先下面之前选一个点的方案数。如果不需要再选择，那么 \(i=0\)。然后我们考虑转移，对于 \(u\) 的一个儿子 \(v\)，我们可以考虑类似树上背包的转移，假设 \(dep_u\) 表示节点 \(u\) 的深度，其中根节点深度为 \(1\)，那么：
\[f'_{u,i}=\sum_{j=0}^{dep_u}f_{u,i}\times f_{v,j}+\sum_{j=0}^if_{u,i}\times f_{v,j}+\sum_{j=0}^{i-1}f_{v,i}\times f_{u,j} \]前面一个 \(\sum\) 是求当前点选择的情况，后面两个是求不选择的情况。我们发现这个东西维护一个前缀和就能够快速求出。我们可以考虑线段树合并，维护区间 dp 值的和。然后合并的时候可以维护两个全局变量表示前缀 \(f_u\) 的和和后缀 \(f_v\) 的和。总体比较好写。
类似题目推荐：P5298 [PKUWC2018]Minimax，期望树形 dp，同样是用线段树合并维护。
P6669 [清华集训2016] 组合数问题
数位 dp，组合数：其实就是 \(C_i^j\equiv 0(\bmod k)\) 的个数。然后用 Lucas 定理拆开：\(C_n^m\equiv \prod C_{a_i}^{b_i}\)。我们发现满足条件必须要这些组合数中必须要有某个 \(C_{a_i}^{b_i}=0\)，因为每个 \(a_i,b_i
如果不会 Lucas 定理，可以看我的 。
P5468 [NOI2019] 回家路线
本题有 加强版，注意两者数据范围不同。
斜率优化，图上 dp：发现转移花里胡哨，我们如果按每个点进行 dp 的话，发现光转移的复杂度就是 \(O(n^2)\) 的，根本吃不消。我们可以考虑把航班设到状态，然后把时间（航班时间）和空间（出发点和终点）放到转移条件。然后我们把转移的式子拆开，发现可以斜率优化，现在开始考虑转移条件。对于每个航班，更新时从出发点更新，完了之后插入到终点，这样就处理好了空间限制。对于时间限制，我们可以用类似扫描线的思路，把每个航班拆成两个，按时间排序。第一次扫到就更新 dp 值，第二次插入到单调队列里。
P3244 [HNOI2015]落忆枫音
普通 dp，计数：对于一个 DAG 上的统计，我们有一个结论：假设点 \(u\) 的入度是 \(d_u\)，那么方案数就是 \(\prod d_u\)，具体就是每个点选择一个父亲。但是新加了一条边 \((s,t)\)，可能会有环，我们要从上述答案中减去环的情况。我们假设这个环上的点为 \(a_1,a_2,\dots,a_k\)，大小为 \(k\)，那么我们住了这个环以外的点乱选，那么要减去的值为 \(\dfrac{\prod d_u}{\prod d_{a_i}}\)。我们发现这个东西可以 dp，我们假设 \(f_u\) 表示从 \(t\) 到 \(u\) 的路径上，该式的值。容易得到 \(f_u=\dfrac{f_v}{d_u}((u,c)\in E)\)，那么答案就是 \(\prod d_u-f_s\)。
SP3734 PERIODNI - Periodni
SPOJ 太奇怪了，所以直接放 luogu 链接了。
笛卡尔树，树形 dp，组合计数：我们发现，如果按照笛卡尔树的思路分割序列，对应的两个子树内是不会互相影响的。建完笛卡尔树之后，我们考虑树上背包。设 \(f_{u,i}\) 表示子树 \(u\) 选 \(i\) 个的方案数。然后随便用组合数统计一下就可以了。
P2605 [ZJOI2010]基站选址
本题同样有加强版
数据结构优化：考虑朴素 dp，设 \(f_{i,j}\) 表示前 \(i\) 个站中，选了 \(j\) 个，其中第 \(i\) 个必选的最小费用，转移显然。发现可以预处理除每一个位置的覆盖范围的边界，使用线段树，每次从 \(f_{i,k}\) 转移到 \(f_{i,k+1}\) 即可。
P2150 [NOI2015] 寿司晚宴
状压 dp，根号分治：首先考虑朴素状压，设 \(f_{i,s1,s2}\) 表示前 \(i\) 个数，其中集合 \(1\) 的质因子集合为 \(s1\)，另外一个为 \(s2\) 的方案数。然后我们发现这个做法到后面会有很多不同的素数，无法状压。但是我们发现一个 \(\le500\) 的数，最多有一个比 \(22\) 大的质因子。我们可以考虑类似根号分治的思路，比 \(22\) 小的部分状压，另外一个部分单独处理。
P4428 [BJOI2018]二进制
ddp 入土题，放一道做代表：考虑不带修的情况，我们简单地设 \(f_{i,\dots}\) 表示前 \(i\) 位某某状态下的情况。然后把它写成转移矩阵的形式，用线段树维护即可。如果出题人丧心病狂的话可以选择放在树上。细节巨多，谨慎入坑。
P5363 [SDOI2019]移动金币
计数 dp，二进制拆分，阶梯博弈：首先第一步阶梯博弈，发现问题相当于把 \(n-m\) 个石子分成若干堆，其中编号为奇数堆的石子有效，然后玩 nim 游戏，求先手必胜方案数。正难则反，我们考虑计算先手必败的方案数，也就是每一位二进制位异或起来都是 \(0\) 的方案数。考虑 dp，设 \(f_{i,j}\) 表示考虑完前 \(i\) 个二进制位，都满足条件，还剩下 \(j\) 个石子可用的方案数，转移和统计答案用组合数，插板法之类的即可。
同款题目：P2490 [SDOI2011]黑白棋，阶梯博弈改成 k-nim 游戏。
CF1067D Computer Game
二分斜优矩乘入土题：本题笔者有幸写过题解，可转至：Luogu 题解区
P2481 [SDOI2010]代码拍卖会
巧妙思路转化，背包 dp：对于一种方案，可以转化成 \(9\) 个形如 \(0000011111111\) 的串相加。然后跑背包，设 \(f_{i,j,s}\) 表示考虑到在余数为 \(i\) 的 \(1\) 的后缀，之前已经放了 \(j\) 个，此时数字 \(\%p=s\) 的方案数，组合数大力转移即可。注意处理循环节的计算，具体见 这篇题解
P7914 [CSP-S 2021] 括号序列
赛时暴力 dp 65pts，没想到优化。
区间 dp：设 \(f_{i,j}\) 表示区间 \([i,j]\) 的方案数。直接转移不好考虑，有很多种情况。赛时想到了一个辅助数组 \(h\) 的方法，但是 \(O(n^4)\)，我们可以把 ***，(...)，(..)..(..)，(..)..(..)**，**(..)..(..)，**(..)..(..)** 的情况全部放到 dp 状态上，然后大力转移即可。
P7961 [NOIP2021] 数列
赛时 AC 太爽了。
高维计数 dp，我们发现 \(S\) 的限制其实是一个二进制进位。发现数据范围极小，排除状压之后，可以考虑高维 dp，所有不好满足的限制全部开维维护。设 \(f_{i,j,x,y}\) 表示 \(S\) 中前 \(i\) 维，选了 \(j\) 个，其中已有 \(x\) 个二进制位为 \(1\)，当前位向下一位进位 \(y\)，然后大力转移即可，同样要用组合计数。
P3554 [POI2013]LUK-Triumphal arch
博弈论 dp 题：发现小 B 肯定不会走回头路，每次小 A 染色可定会把当前点的所有儿子染黑，然后开始布局，先猜出小 B 之后的路径，把空余的机会涂黑未来要涂黑的吗，用一个树形 dp 维护这个过程即可。
P5665 [CSP-S2019] 划分
单调队列优化：其实就是模板题，但是极度卡常。