2025 vertigo - dp，调整与归纳选讲 - lcw

DP Part

• 一些典型的调和级数复杂度，基本上要用到总和为 $s$，$i$ 个物品的最小值的范围在 $[0,\dfrac s i]$ 之间，尝试换维，换状态往这上面靠。
• 转移遇到瓶颈，把一些式子带进去，说不定能化简。

---

这几道之前做过，复习一下，有些做过了我也没放上来，太蠢了。

[集训队互测 2022] Range Minimum Element

构造单射，从小到大填 $a$。假如在填 $v$，下标序列为 $\{p_v\}$，那么所有包含在任意一个 $(p_{v,i},p_{v,i+1})$ 的区间继续填，这个容易用 dp 刻画。$f_{l,r,v}$ 表示在填区间 $[l,r]$，值域为 $v$。注意因为要构成单射，所以要求所有包含在 $[l,r]$ 的区间并为 $[l,r]$，复杂度 $\mathcal O(n^3c)$。看到大值域，单点求值应该不用说啥了，观察一下发现可以拉插，$\mathcal O(n^4)$。

CF722E Research Rover

我觉得可以推容斥系数做？没写过，算了，讲一下主流的两种做法：

令 $f_{i,j}$ 表示在第 $i$ 个关键点，恰好经过了 $j$ 个的方案数，令 $g_{i,j}$ 表示 $i$ 到 $j$ 不经过其他关键点的方案数，有 $f_{i,j}\leftarrow \sum\limits_kf_{k,j-1}g_{k,i}$，$g_{k,i}\leftarrow \text{path}_{k,i}-\sum\limits_tg_{k,t}\text{path}_{t,i}$，$\mathcal O(n^3)$。把后边套到左边，并把第一个转移式子带进去有 $f_{i,j}\leftarrow \sum\limits_kf_{k,j-1}\text{path}_{k,i}-\sum\limits_tf_{t,j}\text{path}_{t,i}$，这两个式子都能暴力枚举，$\mathcal O(n^2\log V)$。

还有一种是反演。$f_i=\sum\limits_{j=i}^n(-1)^{j-i}\dbinom j i g_j$，把右侧的 $(-1)^i$ 提到左边，那么等价于每钦定一个点要 $\times -1$，同时钦定的点里选 $i$ 个要统计到 $f_i$ 里面，也是一样的。

[AGC017F] Zigzag

暴力 $f_{i,j,s}$ 表示考虑前 $i$ 行，目前是第 $j$ 条折线，状态是 $s$ 的方案数，因为判断转移要额外加一维当前和 $j-1$ 线的距离。但是如果 $j-1$ 往左 $j$ 往右，等价于限制从 $j-1$ 下次往右走生效，那就直接抵消掉一个一，正常转移。

QOJ3305 LCS 8

dp of dp。如果 $|i-j|>k$，那么 $f_{i,j}$ 不会贡献到最后状态，所以 dp 到 $i$ 的时候只要存前后 $k$ 个元素，一共 $2k+1$ 个，还有差分数组和 $f_{i,i}$ 的值。

---

接下来是没做过的。

[1] [USACO21DEC] Paired Up P

被紫题爆锤了，把题目抽象成二维表格了，实际上直接正常画就好。$T=1$ 略，$T=2$，最后没匹配的牛序列一定是一段 H 一段 G 交替，同时 H,G 交界处的两头没匹配的牛距离 $>K$。令 $f_{i,j}$ 表示钦定下一头没匹配的牛是 G，且当前已经处理到第 $i$ 头 H，第 $j$ 头 G（这里处理好指前 $i$ 头 H 和前 $j$ 头 G 的匹配对都在当前决策范围内），转移发现是一条对角线上的区间 max，但是有单调性，所以把 bound 算出来直接单点转移，$\mathcal O(n^2)$。

[0] [THUPC 2023 决赛] 老虎机

对于一个固定的答案串 $s\in S$，定义 $V_s$ 表示对应可以确定答案串为 $s$ 的集合，答案为第一次到达 $V_s$ 内任意状态的期望时间。因为如果 $u\in V_s$，那么任意 $u\subseteq v$ 都满足 $v\in V_s$。根据期望的线性性，把式子拆成到每个 $\not\in V_s$ 的状态的概率乘上在这个状态停留的期望时间，容易转移。最后需要预处理每个 $V_s$，令 $f_{S,T}$ 表示已知集合为 $S$，对应知道的数为 $T$，能确定的字符串编号。因为起始状态都是 $f_{U,*}$，所以 $f_S$ 从 $f_{S\cup \text{mex}(S)}$ 转移即可，$\mathcal O(3^n)$。

[3] 【UNR #7】璀璨宝石

非常有启发性。

发现最终答案是 $\max\left(mx, \left\lceil\dfrac {sum} 2\right\rceil\right)$。于是 80 分做法就容易得出了：如果 $\max$ 取得是前面，那开始直接钦定一个种类是 $mx$，令 $f_{i,j,k,l}$ 表示目前桌上有 $i,j$ 两张卡，$mx$ 颜色是 $k$，还有 $l$ 张所需的最小次数。如果取到后面，似乎很难避免不记录 $mx$ 和 $sum$，应该是一个经典的套路，判定转计数，求出次数为 $sum$ 的方案数和最大值为 $mx$ 的方案数，如果减一下 $>0$ 说明答案可以取到 $sum$。 这里还有一个有意思的解法：如果要求取到 $sum$，等价于所有颜色出现次数都要 $\le \dfrac{sum}2$，但是所有颜色次数之和也才 $sum$，**直接记录未免太浪费了，考虑把一些情况合并一下。**对于一个出现次数序列 $\{c\}$，肯定存在一个 $p$，使得 $\sum\limits_{i=1}^{p-1}c_i,\sum\limits_{i=p+1}^{|c|}c_i\le \dfrac{sum}{2}$。于是我们记 $g_{i,j,k,l,p}$ 表示桌上有 $i,j$ 两张卡，钦定断点在 $p$，两个和分别为 $k,l$ 的最小 $sum$。最后可以通过 $c_p$ 和 $\dfrac{sum}{2}$ 的大小关系判定。两种做法时间复杂度均为 $\mathcal O(n^2M^2)$，颜色数算到常数里。

---

瓶颈其实在于我们不知道消除策略：如果对于 $sum$ 的情况，我们找到一个策略，使得两两配对之后，最后只剩 $sum\bmod 2$ 个宝石，那就容易解决。假设我们先一个个随便消除，如果在某个时刻，序列转变为 $mx$ 的情况了，之后肯定都要和 $mx$ 消，而且按照这个策略最后一定是恰好消完的。所以消除过程可以被划分成两个阶段，而且我们求的是最优化，所以可以在任意时刻转移。重新令 $f_{i,j,k,l}$ 表示 $i,j$ 两张卡，此时剩下的宝石颜色为 $k$，数量为 $l$，同时处于乱消阶段的最小代价；$g_{i,j,k,l}$ 表示 $i,j$ 两张卡，非颜色 $k$ 的宝石此时还有 $l$ 个，同时处于对颜色 $k$ 的宝石消除的最小代价。瓶颈在于从 $f$ 转移到 $g$ 需要枚举两种宝石互相匹配的数量，假设加入了颜色为 $k'$，数量为 $l'$ 的宝石，且 $k’\not=k$，有这部分的转移：$\forall 0\le i\le \min(l,l'),f_{*,*,k,l}+i\rightarrow g_{*,*,t,l+l'-2i}$，其中 $t$ 是不同于 $k,k'$ 的颜色。如果有 $l'<l$，那么转移区间是 $[l-l',l+l']$，区间长度固定，可以单调队列优化；如果 $l'\ge l$，转移区间为 $[l'-l,l'+l]$，这个区间一定经过 $l'$，直接从这里断开打 tag，复杂度 $\mathcal O(n^2M\text{poly}(C))$。

上面如果正常写的话应该要有负数下标，还要偏移一个指针，稍微难写了一点。实际上瓶颈在于 $g$ 的转移会出现负数，观察一下如果有这种情况可以直接转移回 $f$，就可以规避了。疑似有带 $M^2$ 的解法加了剪枝跑过去了，就额外判一下 $f$ 有值再转移，如果加入 $0$ 个宝石就不加，也卡不掉。

[3] QOJ10306 黄焖鸡

先考虑如何刻画这个条件。一个序列 $\{a\}$，奇数位之和和偶数位之和必定有一个 $\ge \dfrac{s}{2}$，那么序列是坏的条件就是奇数位和等于偶数位和，同时不存在更优的独立集。假设新的独立集为 $T$，原来的为 $S$，$T$ 一定是在 $S$ 的基础上选择若干个区间 $[l,r]$，并翻转里面选的数的状态得来的，显然可以化简到一个区间，因为我们只关系是否 $>\dfrac s 2$。把区间差分，操作 $[l,r]$ 等价于操作 $[1,r]$ 再操作 $[1,l-1]$，区间就规约到了前缀。后面的条件变成了 $\forall x\in [1,|a|],\sum\limits_{i=1}^x(-1)^{x-i}a_i\ge 0$，否则把 $<0$ 的那个前缀翻转独立集就会更大。

前缀非常好容易刻画顺序结构，我们现在要判定整个序列 $\{a\}$ 是不是极好的。对右端点扫描，动态维护 $d_l$ 表示 $\sum\limits_{i=l}^r(-1)^{r-i}a_i$。如果出现 $d_l<0$，那么之后左端点为 $l$ 的子区间肯定是好的，可以不用管；如果 $d_l=0$，那么 $[l,r]$ 是坏的，序列不合法，否则操作 $d_l\leftarrow a_r-d_l$，$d_r\leftarrow a_r$。发现任意时刻 $d_l\in[1,m]$，那么可以直接压到状态里：令 $f_{i,S}$ 表示考虑了前 $i$ 个数，其中所有 $d_l$ 构成的集合为 $S$，每次转移加入 $x$，然后按照上面操作，这一步可以预处理，复杂度为 $\mathcal O(nm2^m)$。

比较浪费的是我们加入 $x$ 的时候其实并不关心 $>x$ 的数，所以转移的过程中做一个类似 sosdp 的东西，从大到小加入 $x$，转移完 $x$ 之后，把所有 $\max S=x$ 的状态加到 $S\backslash\{x\}$ 上，这样枚举的复杂度就是 $\mathcal O(\sum\limits_{i=0}^m2^i)=\mathcal O(2^m)$，复杂度 $\mathcal O(n2^m)$。

P8554 心跳

[NOI2023] 合并书本

[CSP-S 2019] 树上的数

[省选联考 2022] 最大权独立集问题

[CTS2022] 独立集问题

调整与归纳 Part

[ONTAK2015] Tasowanie

QOJ2555 Two Bullets

[EC Final 2022] Magic

CF906C Party

[AGC035E] Develop

CF1787H Codeforces Scoreboard

「SWTR-8」地地铁铁

[省选联考 2023] 人员调度

P4886 快递员