概述
-
DP 套 DP 通过 DP/DFS 处理出某个复杂 DP 的状态集，构建出对应的 DAG，从而将复杂 DP 的难度有效降低，有时还伴有降低时空复杂度的效果。
-
其实我不是很认同这个名字。在我看来，更应该叫做“建 DAG 优化 DP”。
实现原理
-
其实上面已经说了：
-
1.通过 DP/DFS 预处理出复杂 DP 的所有有效状态，并连边。
-
2.进行复杂 DP。
-
为了便于理解，我们还是直接看例题吧。
例题
炉石
-
题意：
-
双方打牌。
-
一开始，每方有一个奴隶主在场上。
- 奴隶主：随从。生命值为 \(3\)。受攻击时，如果本次攻击没有导致该奴隶主死亡，那么触发他的技能，召唤一个新的满血奴隶主。特别地，每方场上只能同时存在至多 \(7\) 个奴隶主。
-
然后攻击 \(n\) 次。
- 攻击：有 \(\dfrac{2}{3}\) 的概率打到我方随从（等概率选一个），\(1/3\) 的概率打到敌方随从（同上）。容易证明任意时刻双方都总是有随从。
-
-
数据范围：\(n\leqslant 10^9,T\leqslant 5\)，\(T\) 为数据组数。
-
乍一看就是个状压+矩阵快速幂优化/拉插优化，对吧？
-
容易想到 \(4^7\) 的 \(sta\) 记录一方场上的随从情况，但显然不能接受。
-
转化一下，\(7^3\) 的状态记录“有多少个 \(i\) 血的随从”。显然不用记录有多少个 \(0\) 血的，作差即可——其实我们也不关心。
-
但是打敌我概率不一样，很烦。于是我想到了 \(21^3\) 的状态，把每个我方的随从拆成两个。当然，还是炸飞。
-
观察到敌我互不影响，考虑分别 DP。其实相当于攻击我方 \(\dfrac{2n}{3}\) 次，敌方 \(\dfrac{n}{3}\) 次，\(\bmod\ 3\) 的余数可以暴力——很麻烦，但可以试试。
-
好想法，于是我们现在有了 \(7^3\) 的状态，复杂度为 \(T\times a^3\times\log n,a=7^3\)，纸面复杂度 \(60\times 10^8\)。
-
显然还是过不了。怎么办？
-
首先这里有一个小 \(trick\)，构建转移矩阵的时候把挨打概率构建进去。于是没有那个繁琐的暴力了。
-
然后我们终于走到核心：
-
\(7^3\) 的状态其实是比较冗余的。容易证明，三位上的数字的和 \(\leqslant 7\)，故有很多无效状态。
-
我会爆搜！以 \(001\) 为初始状态，暴搜出所有状态并编号，然后连边。
-
实际的结果是，状态数只有 \(119\)。作为对比，\(7^3=343\)。于是我们的纸面复杂度降至 \(2\times 10^8\)，原题时限 \(2s\)，但有理由认为预处理转移矩阵的整二次方幂代替快速幂之后，\(1s\) 也能随便过。实践中，最大点 \(492ms\)。
-
-
从这道题，我们意识到，预处理状态来降低 DP 的状态复杂度，是很有帮助的，尤其是在状态一看就很稀疏的时候。
拳击比赛
-
题意：
-
\(2^n\) 个人打淘汰赛，这些人的实力 \(f_{1\sim 2^n}\) 恰为一个 \(1\sim 2^n\) 的排列。每轮相邻的两个人打，强者必胜。
-
现在实力为 \(1\) 的你买通了 \(m\) 名选手 \(key_{1\sim m}\)，这些被买通的选手如果遇到你，就会打假赛输给你。
-
另外，这些人的前后顺序可以由你随意安排，因为你买通了比赛方。
-
求有多少种安排的方式，可以使得你不仅赢得比赛的冠军，而且被你打败的人的实力构成的数列的最长上升子序列长度 \(\geqslant k\)。
-
-
数据范围：\(1\leqslant k\leqslant n\leqslant 9,m\leqslant 16\)。
-
感觉很难，先试水分析下 \(k=1\) 的情况，则此时问的就是能赢的总方案数呗。
-
考虑先把自己放在 \(1\) 处，把整个淘汰树画出来。
-
发现一个显然的事情：被我打败的每个人依次是一个 \(siz=2^0,2^1,2^2,2^3,...,2^{n-1}\) 的子树的最终赢家，即那么大的子树中的“最强者”。
-
显然状压！考虑到每次要往对应的子树里选比最强者小的人当垫材，设计如下的 dp 状态：
-
\(dp_{i,sta}\) 表示将 \(key\) 按 \(f\) 递增排序后，当前考虑完毕了第 \(i\) 个被买通的人，\(sta\) 对应的那些子树已经填过人了，的方案数。
-
转移较为显然。
-
\(dp_{i,sta}\to dp_{i+1,sta}\)，转移系数为 \(1\)，证明略。
-
\(dp_{i,sta}\to dp_{i+1,sta|2^k(sta\And 2^k=0)}\)，转移系数为 \(C(f_{key_i}-2-sta,2^k-1)\times 2^k!\)，因为有 \(f_{key_i}-1\) 个“垫材”，但要除去 \(1\) 即我，还要除去已有的子树的占用人数，特别的是，这里 \(sta\) 的值恰为其占用的人数，位权为 \(2^k\) 的位恰好对应着 \(siz=2^k\) 的子树。然后内部可以随意排列。
-
-
最后乘上 \(2^n\)，因为从最左边两个 \(siz=2^0\) 到最大的两个 \(siz=2^n-1\) 的子树都可以互相换位。
-
整挺好，\(O(nm\times 2^n)\)，那这样已经有 \(50\text{pts}\) 了。考虑怎么把 \(k\neq 1\) 的情况整进来。
-
传统的求最长上升子序列算法，不管是定长度求最小结尾还是定结尾求最大长度，都绕不过一个问题：他们的序列是静态的。
-
我会动态！拿着这个序列，找到其中最小的，把它插入到对应位置，该位置的值为该位置的前缀最大值 \(+1\)。
-
证明：每个数被插入的时候，已被插入的数一定小于它。则把它接到结尾比它小的，最长的上升子序列后面就可以了。
-
这是定大小插位置。类似地，定位置插大小也行。
-
那好像可做了？这不就是动态维护一个最长上升子序列吗？前一种要求值单调递增，后一种要求位置单调递增...值单调递增？我们不是把 \(key\) 排序了吗？
-
OK！容易想到把 \(dp_{i,sta}\) 中的 \(sta\) 换成那个动态的序列，毕竟前者的 \(0/1\) 对应着后者的 \(0/\text{非}0\)。
-
可是这个复杂度是 \(O(nm\times n^n)\) 的啊！扯呢！
-
你仔细想想，你会发现这个东西状态不多：某一位为 \(8\)，需要它前面依次出现 \(1,2,\dots,7\)。限制很严格，搜一下试试呗？
-
结果状态数只有 \(2\times 10^5\) 左右。随意咯~。
-
注意，这并不是说我们拉一个 DAG 跑 toposort；那个的状态数无法接受（\(\geqslant 10^9\)）。
-
我们是搜出来所有合法的 lis 序列，然后在 \(O(n)\) 地给当前考虑的 \(key\) 找根的时候快速转移到对应状态。
-
这样的状态其实是上面那个 DAG 的集成，即多个实质不同的状态，被抽象为“考虑完前 \(i\) 个，\(sta\) 的子树已经有根”（作为对比，那个 DAG 的状态是严格的“\(sta\) 的子树的根为 xxx”）。所以搜索和 DP 的复杂度都是对的。
-
其实还有一个更优解（在这个数据范围下）：暴力 \(n!\) 求出那 \(m\) 个选的人的相对实力关系，于是容易常数地求最长上升子序列，从而知道这种相对实力关系是否可行，如果可行，计数一下。\(O(n!\times n\log n)\)。
-
需要注意的是，DP 套 DP 的复杂度瓶颈不一定在 DP 上（尽管 DP 的实际复杂度往往比有效状态数要高，在本题中就是那个 \(i\)，有时还有转移复杂度），也有可能在暴搜上——在不能保证只搜到有效状态的时候。
23.1.12 T1 实用和
- 版权原因，请移步查看。同校的可以找我要截图。