DP solution set
george0929
·
·
算法·理论
传统计数
传统的分析性质+计数 DP，DP 本身不算难。需要明确判据并根据判据 DP。
[AGC002F] Leftmost Ball 紫（计数 DP）
白球对其他球的限制是：任意后缀（或前缀）的白球个数大于等于颜色种类数。
只限制后缀也能保证正确性，因此从后往前 DP，并且需要把白球个数和颜色种类数计入状态。
具体地，我们钦定 i 第二次出现的位置小于 i+1 第二次出现的位置。
令 dp_{i,j} 表示填入了 i\sim n 的数字，填入了 j 个白球的方案数，每次钦定填入的第一个球在最前面以避免重复。
转移是简单的。
树上 DP
树上 DP 的本质在于合并子树，明确 DP 的状态定义后通常转移并不困难。
联考 NOIP 模拟 T3（计数，随机选数转排列，树上 DP）
形式化题意
考虑这样的一个算法：
给定树 T，初始时图上所有节点均为白色，计数器 c = 0。不断进行下列操作直到 T 上不存在白色点：
- 从树上所有白色点中随机选择一个点 u，将 u 以及与其有边直接相连的所有白色点 v 全部染黑，并令 c \leftarrow c + 1。
最后返回 c 作为答案。
林尼想知道，对于给定的树 T，算法的正确率是多少，即有多大概率使得算法返回的答案确实为原图的最大独立集大小。
你只需要输出概率对 10 ^ 9 + 7 取模的结果。
记 n 为树的大小，n\leq 5000。
部分分：最大独立集唯一。
题解
首先按照经典套路，将白点选数改成随机一个排列，按排列选数，然后跳过不合法的选择。
这样最终方案和排列构成双射，至此我们完成了概率转计数。
考虑部分分，分析排列性质，首先考虑限制所有独立集的点都被选，但是发现这样不好限制。
考虑限制所有不在独立集的点都不被选，由于是独立集，所以这样限制也是充要的。
记排列的逆为 rk，独立集为 S。一个不是 S 的点 u 不被选，当且仅当存在一个邻域 v，rk_v<rk_u，且 v\in S，这样我们就得到了充要条件。
记 f_{u,i,0/1} 表示子树 u 内，离散化后的 rk_u=i，且如果 u\notin S，是否有 u 的儿子 v，满足 v\in S\land rk_v<rk_u。
转移时如果 u\in S，则直接合并 f_{v,x,1}，对于 f_{v,x,0}，我们需要做的问题如下：
- 合并两个数列，第一个序列的第 x 个位置在第二个序列的第 y 个位置前。
转移时进行树上背包：
f_{u,i+k,1}'=f_{u,i,1}\times f_{v,j,0}\times \binom{i+k-1}{k}\times \binom{sz_u-i+sz_v-k}{sz_u-i}(j> k)
如果 u\notin S，大致同理，当第三维由 0 变 1 时做上面的转移，只是把 > 改为 \leq。
可以前缀和优化做到 O(n^2)。
考虑正解。
类似 DP of DP，先使用最大独立集 DP（g_{u,0/1} 表示 u 子树 u 是否选择）建立出最优转移 DAG，然后在 f 后加一维表示 u 是否属于 S，只进行 DAG 上边的转移即可。
我们无需显式建立 DAG，只需要在往上做独立集 DP 时只转移最优情况即可。
状压 DP
既然都是状压 DP 了，状态设计和转移都十分暴力，主要难点在于把题目转化为可以 DP 的形式，即有限的状态。
QOJ4314（多项式奇偶分离，（多项式）状压 DP）
形式化题意
给定一个所有系数都 \in \{0,1\} 的 n-1 次多项式 P，求 P^{k} 中有多少项的系数为奇数。
#### 题解
考虑快速幂，有两个方向：
- 计算 $f^{2^k}$，卷积。
- 通过 $f^{i}$ 递推到 $f^{2i}$ 和 $f^{2i+1}$。
第一个方向的卷积不保证项数，倒闭。
考虑第二个方向，根据模二性质，有：
$$
f^{2i} (x)=f^{i}(x^2)
\\
f^{2i+1} (x)=f^{i}(x^2)f(x)
$$
考虑 DP，我们无法处理第二个式子后面的 $f(x)$。
正常 DP 思路，把不能处理的东西记到状态里，记 $dp_{i,g}$ 表示 $k$ 的高 $i$ 位的 $f^{?}(x)$ 乘上 $g(x)$ 的 $\text{popcnt}$，$g$ 是一个多项式（额好像记多项式为状态不是很正常，但确实能做）。
推式子。
$$
f^{2i}(x)g(x)=f^{i}(x^2)g(x)
$$
由于是 $popcnt$，$f(x^2)$ 与 $f(x)$ 等价，考虑将 $g$ **奇偶分离**，将式子写成 $f(x^2)$ 的形式。
$$
f^{2i}(x)g(x)=f^{i}(x^2)g(x)=f^{i}(x^2)[F(x^2)+xG(x^2)]\equiv f^{i}(x)F(x)+xf^{i}(x)G(x)
$$
奇偶项相加互不干扰，即 $dp_{i,g}\leftarrow dp_{i-1,F}+dp_{i-1,G}$，其中 $F,G$ 是 $g$ 奇偶分离后的两个多项式。
$f^{2i+1}$ 同理，每次奇偶拆分会将项数除以二，因此 $g$ 的项数不超过 $n$，状压存 $g$ 即可。
需要预处理所有 $g$ 所拆成的 $F$ 和 $G$。
### [AT_agc020_f [AGC020F] Arcs on a Circle](https://atcoder.jp/contests/agc020/tasks/agc020_f) 黑（状压 DP，实数处理技巧，DP 转移处理）
**小数处理技巧**：暴力枚举 $N$ 个数小数部分的排名。
枚举完把小数部分离散化一下变为 $NC$ 个点，状压 DP 即可。
注意要先让最长的线段放置，要不然可能存在线段绕环大半圈后回来的情况，此时 DP 有后效性。
DP 时按照线段的左端点为顺序转移，避免计重。
## 子问题划分
有些 DP 题的难点在于子问题划分，可以通过手玩样例或者考虑去掉一个元素后解的形态来确定子问题。
### [CF1792F1 Graph Coloring (easy version)](https://codeforces.com/problemset/problem/1792/F1) *2700（补图性质，计数 DP）
红蓝互为补图，因此红蓝都不连通的情况不存在。
第一反应是对红蓝都连通的情况容斥，但是发现这样根本做不了。
不妨转化为有一个颜色不连通，对恰有一种颜色**不连通**的情况计数，此时另一种颜色必定连通。
令 $f_i$ 表示 $i$ 个点，每个子集满足蓝色不连通的方案数，枚举与 $1$ 相连极大的蓝色连通块 $S$，保证跨过 $S$ 和 $[1,i]/S$ 的集合中不存在红蓝都连通的集合，这个连通块需要满足红色不连通，用“极大”保证不重。
由于是"极大连通块"，所以两个集合之间的连边方案是固定的，只能是红色边。
恰好，这样的连边方式满足【跨过 $S$ 和 $[1,i]/S$ 的集合中不存在红蓝都连通的集合】，因此逻辑以一种很奇怪的方式自洽了。
由于对称性，红色不连通方案数 $=$ 蓝色不连通方案数。
则 $f_i=\sum\limits_{j=1}^{n-1}\binom{i-1}{j-1}\times f_{j}\times (2f_{n-j}-[n-j=1])$。
乘二是因为当集合有边时可以任意交换红蓝。
### [CF251E Tree and Table](https://codeforces.com/problemset/problem/251/E) *3000（子问题划分，分类讨论）
注意到树的度数不超过 $4$。
当树是一条链时，分类讨论，一定是从某点开始走到头，拐回来走一段之后开始走折线，简单讨论后发现答案是 $2(n^2-n+2)$，注意链可以翻转，翻转后算不同的方案。
对于一般情况，先放入一个三度点，设其为树根。
当根存在一个儿子是叶子时，两侧被划分为了两个子问题，否则枚举儿子放在哪边，也是两个子问题。
容易发现我们有两种不同的子问题：
- 矩形左上（或左下）有一个点，要用这个点的子树铺成一个矩形。
- 矩形左上和左下各有一个点，要用这两个点的子树铺成一个矩形。
设第一种为 $F(u)$，第二种为 $G(u,v)$。
先讨论 $F(x)$（假设 $x$ 在左上）。
- 如果 $x$ 没有儿子，则无解。
- 如果 $sz_x=2$，答案为 $1$。
- 如果 $x$ 有两个儿子，则枚举两个儿子是怎么放置的，设放在下面的为 $u$，右边的为 $v$。
- 当 $u$ 的儿子个数为 $0$，答案加上 $F(v)$。
- 否则，$u$ 的儿子个数必为 $1$，答案加上 $G(v,son_u)$。
- 如果 $x$ 有一个儿子：
- 若子树 $x$ 为一条链，答案为 $\frac{sz_{x}}{2}$。
- 若 $son_x$ 放在下面，答案加上 $F(son_{son_x})$。
- 否则找到最浅的有两个儿子的点，设其为 $y$，一直直走直到遇到这个点停止，枚举哪个点向下拐。
- 如果向下拐的点（设其为 $z=son_{y,0}$）有一个儿子，判断一下它能不能把第二行的前缀填满，如果可以，答案加上 $F(son_{y,1})$。
- 否则，枚举一下哪个儿子（设其为 $son_{z,0}$）能把第二行的前缀填满，如果可以，答案加上的 $G(son_{y,1},son_{z,1})$。
再讨论 $G(x,y)$。
- 如果 $x,y$ 没有儿子，答案为 $1$。
- 如果 $x,y$ 各有一个儿子，答案为 $G(son_x,son_y)$。
- 否则，设 $x$ 有一个儿子，答案为 $F(son_x)$。
复杂度看似 $O(n^2)$，但是提交后直接过了。
因为 $G(u,v)$ 被调用时，两个点的深度差不超过 $1$，每次 $G$ 往后转移只有一个后继，而这颗树每层节点个数是 $O(1)$ 的（似乎最多 $6$），因此 $G$ 的总状态是 $O(n)$ 的。
## 对解的生成方式 DP
这类 DP 的难点在于设计一个解的生成方式，并根据生成方式 DP。
通常常用的技巧有分布转移和操作后置。
### [CF2068D Morse Code](https://codeforces.com/problemset/problem/2068/D) *3100（DP 贡献计算技巧，分步转移）
感觉还是对 DP 过程中算贡献和分布转移的理解不是很深刻。
对二叉树形态 DP，由于节点放置不连续，显然要按深度 DP。
$f_{i,j,k,l}$ 表示 $i$ 个叶子，$j$ 个最大深度的叶子，$k$ 个次大深度的叶子，最大深度是 $l$，可以做到 $O(n^5)$。
我尝试了在转移时算贡献，但是没有成功，因为最终排名不确定。
事实上，DP 过程中算贡献和分布转移本质上是让每个点实时有贡献，并且固定一些点停止贡献。
对于扩展深度为 $2$ 的点，我们并不用管，因为我们每次只会把点的最浅深度集体下移 $1$，且点只有在作为最浅深度时才会被固定。
**因此这个点的实际深度就是这个点（这个点不存在时我们认为这个点的祖先就是这个点）在状态里的时间 $-1$**。
令 $f_{i,j,k}$ 表示固定了 $i$ 个叶子不再扩展，在未固定的叶子中有 $j$ 个最大深度、$k$ 个次大深度的叶子。
则要么固定一个次大深度的叶子，要么把次大深度的叶子全部扩展。
$$
f_{i,j,k}\to f_{i+1,j,k-1}
\\
f_{i,j,k}+w\to f_{i,k,j+k}
$$
$w$ 表示 $p$ 的第 $i+1\sim n$ 大的和，答案为 $f_{n,0,0}$，构造方案是简单的。
$O(n^3)$。
`double` 要加上 $0.5$ 再转为 `int` 啊啊啊。
### [P11802 【MX-X9-T6】『GROI-R3』Graph](https://www.luogu.com.cn/problem/P11802) 紫（分析性质，计数 DP，分步转移）
模拟赛赛时认为 $\gcd$ 必须等于 $1$，爆零了/ll。
看来考试时要把发现结论的依据写一写（周期结论）。
首先由题意，$G$ 上任意一个点能走到他自己，因此 $G$ 是若干环的并。
得到 $\gcd=1$ 的错误结论是由于周期结论的直觉，让我们仔细想想这个结论能带给我们什么信息。
对于 $G$ 上一个长为 $len$ 的环，我们从一个点出发，每次走 $k$ 步，能得到 $\gcd(k,len)$ 个长为 $\frac{len}{\gcd(k,len)}$ 的环。
因此，我们还可以选择**把若干个相同长度的环在 $G$ 中拼在一起**。
具体地，用若干个长度为 $i$ 的环拼成长为 $i\times t$ 的大环，则有：
$$
\frac{it}{\gcd(k,len)}=i
\\
t=\gcd(k,it)
\\
\gcd(\frac{k}{t},i)=1
$$
因此，设 $cntloop_i$ 表示环长为 $i$ 的环数，找到最小的 $t$ 使得 $\gcd(\frac{k}{t},i)=1$，则 $t|cntloop_i$。这个条件是充要的。
考虑计数 DP。
按链 id DP要记录每个环长的 $cnt$，不可接受。
因此考虑**按需要记录的值** DP，这样的好处是我们可以在进行 $i\to i+1$ 的转移时顺便判断 $i$ 是否合法。
令 $f_{i,j,k}$ 表示当前处理长度 $i$，长度为 $i$ 的链有 $j$ 个，有 $k$ 个剩余孤点（记录长度 $\leq j$ 的链个数不容易保证不重不漏，因此选择 $=$ 的定义）。
有一个技巧：我们可以把没有闭合的链各加上一个孤点，以保证 $i$ 增加时链长 $=i$ 的定义。
然而 $w$ 个孤点在环上的贡献为 $w!$，这要求了我们不能实时计算这个贡献，只能在最后计算。
具体地，我们在转移时不区分孤点，最后乘上孤点个数的阶乘，根据组合意义，这个方法在**不存在全是孤点组成的环**时正确。
在孤点成环时，我们发现是阶乘和圆排列的区别。
具体地，对于一个 $x$，设长为 $x$ 的全孤点环为 $y$ 个，则我们多算了 $x^y y!$ 倍，因为我们要：
- 除掉圆排列的循环。
- 当孤点都相同时，这些环没有顺序之分，除掉【最后乘上孤点个数的阶乘】对这些环顺序的错误贡献。
我们尝试用分步的思想来推导 DP 转移方程。
- 加入原图上的长为 $i$ 的链，这一步是模拟题意。$f_{i,j,k}\to f'_{i,j+cntlink_i,k}$（$cntlink_i$ 指原图上长为 $i$ 的链个数）。
- 求出最小的 $t$ 使得 $\gcd(\frac{k}{t},i)=1$，加入一些环，满足长为 $i$ 的总环数是 $t$ 的倍数，形成环有如下两种方式：
- 选出若干孤点构成环。
- 将已有的链闭合形成环。
即枚举 $c,l$，$\frac{f'_{i,j,k}\binom{j}{l}}{i^c c!}\to f''_{i,j-l,k-ic}$，转移条件是 $(cntloop_i+l+c)\bmod t=0$。
- 把没有闭合的链加上一个孤点，$f''_{i,j,k}\to f_{i+1,j,k-j}$。
记孤点个数为 $cnt1$，答案即为 $f_{n+1,0,0}\times cnt1!$。
分析复杂度，有 $ij\leq n,ic\leq k\leq n,l\leq j$。
$ij,ic,il$ 各贡献 $\sum \frac{n}{i}$，$k$ 贡献 $n$。
总复杂度 $O(n\sum\frac{n^3}{i^3})=O(n^4\sum\frac{1}{i^3})=O(n^4)$。
在推导时，我们发现没有转移条件时完全可以把【选出若干孤点构成环】和【将已有的链闭合形成环】分步转移做到 $O(n^3)$。
把条件改成 $-cntloop_i-l=c\pmod t$ 仍然可以分步转移，枚举 $cntloop_i+l\bmod t$ 的值做若干遍即可。
### [P9523 [JOIST 2022] 复制粘贴 3 / Copy and Paste 3](https://www.luogu.com.cn/problem/P9523) 紫（区间 DP，简化转移，操作后置，调和级数）
这个操作看起来就很符合区间 DP 的形式。
令 $dp_{l,r}$ 表示 $[l,r]$ 的生成代价，一个区间形如 $??? [Y] ??? [Y] ?? [Y] ???$，即若干个字符加上若干个剪切板字符串。
转移时枚举第一个 $[Y]$ 的位置可以做到 $O(n^4)$，考虑简化转移，要求转移到的区间末尾是 $[Y]$，再用区间扩展转移实现往后加 $?$，可以做到 $O(n^3)$。
我们的贡献和字符串 $Y$ 在 $[l,r]$ 的出现次数有关，考虑反过来刷表，枚举出现次数以做到调和级数的复杂度。
$$
dp_{l,r}+B+C(\text{occur}(s[x:r],s[l:r]))+A(r-x+1-\text{occur}(s[x:r],s[l:r])\times (r-l+1))\to dp_{x,r}\ \ (x\leq l)
\\
dp_{l,r}\to dp_{l,r+1}
$$
我们发现我们还要处理 $[x,r]$ 开头 $?$ 段，可以上数据结构做到双 $\log$，但是无法通过。
**Hint：**将操作 A 后置，即允许在字符串开头添加字符。
即 $dp_{l,r}\to dp_{l-1,r}$，这相当于把操作 A 在操作序列中插入到了头部。
这样我们只需要枚举 $O(n\ln n)$ 个 $x$，复杂度 $O(n^2\ln n)$。
后置操作 A 本质上就是我们新加入了一个操作 D 是在串前加入字符，然后发现和原问题等价。
实际写的时候写的是 $dp_{l,r}\to dp_{l,x}\ \ (x>r)$，总之是等价的。
## 匹配型 DP 与贡献后置
匹配型 DP 即对一个匹配方案 DP，较为常见的对排列 DP 本质上也是匹配型 DP。
通常转移是无法保证已经扫到的元素全部被匹配的，需要记录失配数，即把失配点的贡献后置处理。
当然贡献后置的技巧不只局限于记录失配数，所有无法当前处理的转移 case 都可以考虑使用贡献后置。
### [P4859 已经没有什么好害怕的了](https://www.luogu.com.cn/problem/P4859) 紫（二项式反演，匹配型 DP）
令 $t=\frac{n-k}{2}$。
二项式反演，钦定 $i$ 个 $a>b$，其余不管的方案数为 $g_i$，则 $ans=\sum\limits_{i=t}^{n} \binom{i}{t}(-1)^{i-t}g_i$。
匹配型 DP 求出 $g_i$，具体地令 $f_{i,j}$ 表示 $b[1\sim i]$ 中有 $j$ 个匹配了比他小的 $a$ 的方案数，限制由严到松，因此转移是容易的。
最后 $g_i=f_{n,i}\times \color{red}(n-i)!$，不要忘了这个系数，表示其余的匹配任意。
### [P14424 [JOISC 2014] 邮戳收集 / Collecting Stamps](https://www.luogu.com.cn/problem/P14424) 紫（贡献后置，状态简化）
#### 题意配图
#### 题解
经过一个邮戳台有四种方式：
1. $u+e$。
1. $d+v$。
1. $u+v$。
1. $e+d$。
考虑在东向电车行走的路线，可以跳过若干邮戳台不走，其余走 $u+v$，或者走 $u+e$ 上去，把没走的邮戳台挑若干个走 $e+d$，挑一个走 $d+v$ 下去。
注意 $u+e$ 和 $d+v$ 可能被走多次。
将 $e+d$ 和 $d+v$ 的贡献后置，在转移时加上额外贡献，令 $f_{i,j,k}$ 表示到了站台 $i$，有 $j$ 个邮戳台被指定走 $d+e$，$k$ 个邮戳台被指定走 $d+v$，转移时加上 $2T(j+k)$ 的贡献，枚举当前有 $k_1$ 个 $u+e$ 和前面匹配，$k_2$ 个 $d+v$ 和后面匹配。可以做到 $O(\text{poly}(n))$。
**简化状态**，由于在上面只能往左走，因此只有存在没有匹配的 $d+v$ 时才能匹配存在未匹配的 $d+e$，另一方面，我们做 $u+e$ 和 $d+v$ 的匹配时实际上顺便把 $d+e$ 走了，可以把向上和向下理解称括号匹配，当存在未匹配的左括号时可以选择 $d+e$。
令 $dp_{i,j}$ 表示到了站台 $i$，有 $j$ 个未匹配的 $d+v$ 的最小代价。
转移时，可以选择 $u+v$，当 $j>0$ 时可以选择 $d+e$。枚举这个站台有 $k1$ 个 $u+e$ 和前面匹配，$k2$ 个 $d+v$ 和后面匹配，转移到 $dp_{i+1,j-k1}$ 或 $dp_{i+1,j+k2}$。
前缀和优化可以做到 $O(n^2)$。
### [[CSP-S 2025] employ](https://www.luogu.com.cn/problem/P14364) 紫（贡献后置，匹配型 DP）
会了贡献后置但是不会推式子，要练组合数学了。
首先这是一个匹配问题，具体匹配方案如下：
- 当这个点值为 $1$，且有人被录取时，匹配一个 $c$ 大于【之前失败人数】的人。
- 当这个点值为 $1$，且无人被录取时，匹配一个 $c$ 小于等于【之前失败人数】的人。
- 当这个点值为 $0$ 时，匹配任意一个人。
匹配问题考虑 DP + 贡献后置，按 $c$ 的值 DP，令 $f_{i,j,k}$ 表示 $[1,i]$ 拒绝 $j$ 个人，匹配了 $k$ 个 $c>j$ 的人的方案数。
$j$ 既代表当前拒绝的人数，也代表 $c$ 匹配到的值，在本题中可以合并成一维状态。
记 $cnt_i=\sum\limits_x [c_x=i],pre_i=\sum\limits_{x=1}^{i} cnt_x$。
$\sum [s_i=1]\leq 18$ 的部分分启示我们暴力枚举每个点的状态：
- $s_i=1$，实际有人录取，则有：$$f_{i,j,k}\to f_{i+1,j,k+1}$$
$\tiny{\text{以上是我自己会的部分 qwq}}$。
- $s_i=1$，实际无人录取，有一个 $\leq j$ 的 $c$ 与当前位匹配，有 $j\to j+1$，那么我们要枚举 $c=j+1$ 的有多少和前面匹配，则有：$$\sum\limits_{w=1}^{\min(k,cnt_{j+1})} f_{i,j,k}\binom{k}{w}\binom{cnt_{j+1}}{w}w!(pre_j-(i-k))\to f_{i+1,j,k-w}$$
- $s_i=1$，有 $j\to j+1$，那么我们要枚举 $c=j+1$ 的有多少和前面匹配，并且我们要讨论与这个位置匹配的人的 $c$ 是否 $>j+1$。
- 当 $c>j+1$ 时：$$\sum\limits_{w=1}^{\min(k,cnt_{j+1})} f_{i,j,k}\binom{k}{w}\binom{cnt_{j+1}}{w}w!\to f_{i+1,j+1,k-w+1}$$
- 当 $c\leq j+1$ 时：$$\sum\limits_{w=1}^{\min(k,cnt_{j+1})} f_{i,j,k}\binom{k}{w}\binom{cnt_{j+1}}{w}w!(pre_{j+1}-(i-(k-w)))\to f_{i+1,j+1,k-w}$$
讨论到这里，我们发现已经没有必要枚举每个点状态了，直接转移所有可能的情况就做完了。
注意统计答案时必须要求 $k=n-pre_j$。
### [P7213 [JOISC 2020] 最古の遺跡 3](https://www.luogu.com.cn/problem/P7213) 黑（分析性质，贡献后置，子问题划分）
> 当然贡献后置的技巧不只局限于记录失配数，所有无法当前处理的转移 case 都可以考虑使用贡献后置。
令 $b_i$ 表示第 $i$ 个石柱最后的高度，根据题意有且仅有 $b_{A_i}\neq 0$。
考虑如何从 $h$ 求 $b$，首先我们发现最后 $b$ 会变成一个排列，因为每次都会固定 $1\sim N$ 恰一个数不动。排列继续进行操作不会受任何影响，所以进行 $N$ 次操作等价于不断进行操作。
模拟一下发现每个时刻相同高度的石柱最多有两个，且下一步前面的石柱高度会减一。
一个石柱从不变到减少的状态转变，当且仅当：
- 后面某个石柱上一步减少到了这个高度，之后由于相同高度的石柱最多有两个，因此后面的石柱被固定，前面的石柱开始减少。
- 石柱减少到某个位置，后面不存在高度相同的石柱，石柱被固定。
容易发现，高度为 $i$ 的石柱位置会不断前移，严谨的说：
- 一个后缀中如果出现了高度为 $i$ 的石柱，则这个后缀在接下来的时间里必定含有高度为 $i$ 的石柱。
- 反之，一个后缀中没有出现高度为 $i$ 的石柱，则这个后缀在之前也没有出现过高度为 $i$ 的石柱。
从后往前考虑，如果 $i$ 后面的 $b$ 出现了 $1\sim h_i$ 的所有整数，那么 $b_i=0$，否则，记 $x$ 表示满足以下条件的最大整数：
- $x\in[1,h_i]$。
- 不存在 $b_j=x\land j>i$。
那么 $b_i=x$，因为上述条件表示 $i$ 后面高度为 $x$ 的石柱从未出现过，那么 $i$ 必定变为高度为 $x$ 的石柱。
现在我们知道了 $N$ 个 $b\neq 0$ 的位置，我们需要对 $h$ 计数。
但是我们不知道如何根据 $b$ 求 $h$ 的方案数，所以直接对 $b$ 的排列进行计数的方法是没有前途的。
考虑直接对 $h$ DP，模拟 $b$ 的生成方式，具体地令 $f_{i,j}$ 表示 $[i,n]$ 中，$b$ 出现了 $1\sim n$ 的所有整数，所对应 $h$ 的方案数。
我们要干的事情是对 $h$ 进行匹配计数，$1\sim N$ 的每个数可以被匹配两次，我们记 $cnt0_i$ 表示 $1\sim i$ 中 $b=0$ 的位置个数。
核心思想：贡献前置、不同高度之间的独立性。
为了计算可以填数的数量，我们把两个相同的 $i$ 视作本质不同的数字，最后除以 $2^n$。
讨论 $b_i$：
- 当 $b_i=0$ 时，$h_i\leq j$，$f_{i,j}\leftarrow f_{i+1,j}\times (2j-(j+cnt0_{n}-cnt0_{i}))$，表示匹配一个 $\leq j$ 的数，$\leq j$ 的中 $j$ 个数已经被用掉并且 $b\neq 0$、$cnt0_{n}-cnt0_{i}$ 个数被用掉且 $b=0$。由于 $j$ 在从后往前的模拟中递增，限制由紧到松，因此转移逻辑自洽。
- 当 $b_i\neq 0$ 时：
- 当 $b_i>j+1$ 时，考虑**延迟贡献**这一部分，先不管，$f_{i,j}\leftarrow f_{i+1,j}$。
- 当 $b_i=j+1$ 时，如果 $[j+2,k]$ 在后面都出现过且 $k+1$ 没有出现过，则 $f_{i,k}\leftarrow f_{i+1,j}$。在这里，我们需要处理之前 $h_i>j+1$ 所带来的贡献。有 $j+1\leq b_i\leq k$。
- 枚举 $k$，计算 $[j+2,k]$ 都出现的方案数，这部分与之前的状态独立，因此可以直接乘起来。
- 记 $suf_1=(n-i)-(cnt0_n-cnt0_i)$，我们需要在 $j-suf_1$ 个数中选 $k-j-1$ 个数，要求这 $k-j-1$ 个数排成连续段，则有 $f_{i,k}\leftarrow f_{i+1,j}\binom{suf_1-j}{k-j-1}(2(k-j+1)-(k-j-1))g_{k-j-1}$，其中 $g_i$ 表示 $i$ 个数最后形成的 $b$ 排成连续段的方案数。容易发现在这次转移后所有未确定的石柱高度都 $>k$，所以这些石柱不会对当前 $k-j-1$ 个数排成连续段造成任何影响，即 $g$ 完全独立。
考虑如何求 $g_i$。考虑**类似区间 DP 的子问题划分结构**，枚举最后一个被固定的石柱的高度，$g_{i}=\sum\limits_{j=1}^{i} g_{j-1}g_{i-j}\binom{i-1}{j-1}(2(i-j+1)-(i-j))$。
时间复杂度 $O(N^3)$，常数极小可以通过。
本题的启示：
1. 当 DP 遇到无法处理的 case 时（通常是对另一种转移有后效性），不管这个贡献，放到受影响的转移 case 中后置处理。
2. 不知道如何拆分子问题时，可以考查个别数，例如如果把第一个/最后一个满足某条件的元素拿走会怎么样。
## 数据结构/贪心思想辅助 DP
这类问题难点不在 DP，主要在于使用贪心思想简化问题或使用数据结构大力优化。
传统的 DS 优化 DP 太常见了，这里放一个不是很常见的套路。
### [CF1610G AmShZ Wins a Bet](https://codeforces.com/problemset/problem/1610/G) *3300（贪心，trie+hash，DP）
#### 形式化题意
给定一个括号串 $S$，每次可以删去一个 $()$ **子序列**，求能得到的最小字典序字符串。
$1\leq |S|\leq 3\times 10^5
题解
对于本题，只有后缀的局部最优等于整体最优。
首先删除一个左括号时，贪心地，肯定删除最前的右括号。
并且我们可以把删去一个左括号等价为删除这个左括号连续段中最后一个左括号。
那么我们可以把题目中的子序列改为子串。
那么我们删去一个左括号时，一定会删除后面极短的合法括号串。
删一个合法括号串后变为子问题，考虑 DP，令 f_i 表示 [1,i] 的答案，记 lst_i 表示第 i 个字符向前极短的括号串为 [lst_i,i]（若 S_i=( 则 lst_i=-1）。
在 S_i=( 时转移是唯一的。
在 S_i=) 时有：
f_{i}=\min(f_{lst_i-1},f_{i-1}+S_i)
把所有 f 放到 trie 上，相当于动态加叶子的 trie，可以求 \text{lca} 快速比较字典序。
但是，这是错的。
因为我们对前缀进行 DP 时，局部最优不等于整体最优，比如 (((()))))，则应该不删任何东西，但是我们会令 f_8=\emptyset，f_9=)。
本质上是我们删完前缀的后缀时不知道后面拼接的是啥，后面拼的字符可能影响最优性，局部最优不等于整体最优。
考虑对后缀 DP，则：
f_{i}=\min(f_{nxt_i+1},S_i+f_{i+1})
需要在反 trie 上加叶子，那么在反 trie 上倍增倍增维护哈希即可。
后缀 DP 的好处是删完后缀的前缀时知道后面拼什么，而前面拼什么不影响后缀串的最优性，因此是正确的。