author:
- Kelvin
date: 2022.01.25
title: WC2022「dmy杂题选讲」笔记
DP 状态设计
求"满足某种条件的子串/子序列"的长度和、个数。
若无思路可以先考虑如何判断合法，再试图通过 DP 求得答案。
Stars
一颗星星可以抽象成 K 维空间中的一个整点。称若干星星构成的集合S
是奇妙的，当且仅当存在 K 维空间中的整点 P（P
处可以有星星也可以没有），P 与 S 中的每颗星星至少有一维坐标相同。有一个长度为 N 的星星序列 A，请你求出所有奇妙子段的长度之和。
\(N \le 10^5\) , \(K \le 5\)
如何判断合法：
对于一个串，枚举 \(1\) \(K\) 的排列
\(P\)，每次检查一个数时，若其无法被已有的各坐标匹配， 则取出 \(P\)
的第一个数 \(t\)（讲师称之为"锦囊"）后删去 ，将当前数的 \(t\)
坐标加入匹配坐标内。 若对所有 \(P\) 已空且串仍未匹配完则不合法。
做法：
DP，设 \(f_{i,S}\) 为从第 \(i\) 位开始，锦囊顺序为 \(S\) （也就是上文的 \(P\)
），合法的最远右端点。
机房讨论得出结果如下
考虑转移：我们知道点 \(i\) 处一定使用了锦囊 \(S_1\)
，那么考虑将此位删去，即将 \(S_1\) 的使用延后。 枚举中途使用的锦囊个数 \(j\)
，找到最近的一个只能被 \(S_1\) 匹配（与 \(i\) ）的点，将 \(S_1\) 插入到 \(S_j\)
后，意即在此时使用锦囊 \(S_1\) ，如此可以保证锦囊的使用与从 \(i\)
开始是相同的。
「PA 2021」Od deski do deski
有 \(n\) 棵树，每棵树有可能是 \(m\) 种之一。
小 C 每天可以选择连续的一段树砍掉：要求这一段的长度至少是
\(2\)，并且第一棵与最后一棵种类相同。问有多少种初始局面，使得存在一种方法通过若干天将树砍光。对 \(10^9 + 7\)
取模。\(n \le 3000, m \le 10^9\)
如何判断合法：
若该局面可被划分成若干段，每段都符合砍掉的条件，则合法。
因为任意两次砍树不会相交，也不会包含（可将被包含者忽略）。
具体地，将树的种类看成颜色，设 \(dp_{i}=0/1\) 为前 \(i\)
位是否能被划分，可从前面与 \(i\) 颜色相同的点转移过来。 那么我们设 \(S\)
为前面每个合法划分后面所跟的颜色，即为当前 \(i\) 所能选的颜色。
做法：
设 \(f_{i,j,0/1}\) 为前 \(i\) 位 是/否 一个合法划分，\(i+1\) 可用颜色个数有
\(j\) 个 时的方案数。
转移显然。
DP 优化技巧
观察性质/简化
AGC044E
圆上有 \(N\) 个点，你初始随机出生在一个点。
第 \(i\) 号点有属性 \(A_i\), \(B_i\)。如果你当前处在 \(i\) 号点，你可以选择结
束游戏并获得 \(A_i\) 元，或者花费 \(B_i\) 元将自己随机移动到左右两
点中的一个。求最优策略的期望收益。收益为得到的钱减付出的钱。
输出实数，绝对或相对误差在 1e-10 以内即算正确。
\(N <= 2 \times 10^5, 1 <= A_i <= 10^{12}, 1 <= B_i <= 100\)
容易联想到一道题：「USACO18DEC」Balance Beam
P（gmoj「鱼戏团表演」）
那道题的转移是
\(f_i=\max\left(A_i , \frac{1}{2}(f_{i-1} + f_{i+1})\right)\) ，看成 \(n\)
个二位数点 \((i,f_i)\)，可以通过维护上凸壳解决。 回看这道题，转移是
\(f_i=\max\left( A_i , \frac12(f_{i-1}+f_{i+1}) - B_i \right)\) ，这个
\(B_i\) 就很碍事。
考虑设 \(T_i = f_i + C_i\) ，\(C_i\) 是未知的常数， 满足上式的形式（无
\(B_i\)）， 那么有
即
\[f_i =\max \left( A_i - C_i, \frac12 \left( f_{i-1}+C_{i-1} + f_{i+1}+C_{i+1} \right) - B_i - C_i\right) \]为了去除 \(B_i\) 的影响，则有
\(C_{i-1}+C_{i+1} = 2 \left( B_i + C_i \right)\) 。
由于本题在环上，可考虑破环成链，那么元的数量是比方程数量多 \(2\)
的，于是可钦定两值，递推求出剩余，一个位置对应两点取 \(f\) 较大值即可。