Front
对 zjk 的 Basic Dynamic Programming Side A 的补充、总结以及 Code。
Side A:
DP 状态设计。
常见的 DP 状态
树
树上 DP 常见的状态是考虑子树内的情况，然后通过子树的状态向上合并。复杂度一般是 \(O(n^3)\) ，一些特殊的 DP 转移方程通常可以通过分析优化掉一个 \(n\) 。
但是树上 DP 同样可以考虑自上而下的合并。
例1
题面
给一棵 \(n\) 个点的有根树，点有点权，求包含根权总和不超过 \(m\) 的连通块数量。
\(n \leq 10^3, m \leq 10^5\)
思路
考虑 dfs 序优化。
将点按照 dfs 序排列。
此时对于点 \(u\) 相当于决策于选择与否。若选，则考虑下一个点；否则，直接跳出以 \(u\) 为根的子树，向后考虑。记 \(f_{u, k}\) 表示考虑 dfs 序前 \(u - 1\) 个点，一共选了 \(k\) 个点的合法连通块数。记 \(s_u\) 表示以 \(u\) 为根的子树大小。
具体体现在 DP 上，考虑填表转移即：
\[\begin{aligned} & \text{init: } f_{1,0}=1 \\ & f_{u+1,k+1} \mathop{\leftarrow} \limits^{+} f_{u,k} \\ & f_{u+s[u],k} \mathop{\leftarrow} \limits^{+} f_{u,k} \\ \end{aligned} \]最后的答案即：
\[Answer = \sum_{i=1}^m {f_{n+1,i}} \]正确性显然。
dfs 的想法比较显然，但用法很广泛，在 \(O(n^3) \rightarrow O(n^2)\) 甚至 \(O(n^2) \rightarrow O(n)\) （好像没见过）的优化上有奇效。
数位 DP
在某一进制 \(k\) 下考虑一些数。
考虑从低到高或从高到低填所有数的每一位。
一般有大于小于等于的限制，也会有位运算的限制，需具体考虑，一般从高到低记录大小状态并填数。
加法的相关选择也可以处理，**常见操作是从低到高，记录后面加起来进了多少位。也可以从高往低做：状态中钦定后面进了多少位，但是复杂度 UP **。
例1 - loj#3215./luoguP5985 「PA 2019」Muzyka pop
题面
给一个长度为 \(n\) 的序列 \(v\) 和一个 \(m\) ，找到一个长度为 \(n\) 的序列 \(a\) 使得：
\[0 \leq a_1 < a_2 < \cdots < a_{n-1} < a_n \leq m \]求最大化的：
\[\sum_{i=1}^n \mathrm{popcount}(a_i)\cdot v_i \]\(1\le n\le 200\)，\(n-1\le m\le 10^{18}\)，\(|a_i|\le 10^{14}\)
思路
考虑优先满足不等式的条件。
对于最高位 \(u\)，\(a_i\) 上的划分情况显然是：
\[\mathop{00...00} \limits^t | \mathop{11...11} \limits^{n-t} \]于是对于最高位 \(u\) 相同的 \(a_i\) ，创建子问题并去掉这些 \(a_i\) 的第 \(u\) 位，然后解决子问题。
所以考虑区间 DP ，记 \(f_{l,r,k,0/1}\) 表示 \([l,r]\) 区间中考虑低 \(k\) 位（这部分是数位 DP），高位与 \(m\) 是否相等的最大值：
\[\begin{aligned} & \text{init: } \forall r-l=0:f_{l,r,0,0}=\max(0,v_l),f_{l,r,0,1}=[m\;\text{is odd}]v_l \\ & \text{init: } \forall r-l=1:f_{l,r,0,0}=v_r,f_{l,r,0,1}=\begin{cases} v_r & m\;\text{is odd} \\ - inf & \mathrm{otherwise} \end{cases} \\ & \text{init: } \forall r-l>1:f_{l,r,0,0}=f_{l,r,0,1}=-inf \\ & f_{l,r,k,0}=\max_{i=l-1}^r (f_{l,i,k-1,0} + f_{i + 1,r, k-1,0}+\sum_{j=i+1}^r v_j) \\ & f_{l,r,k,1}= \begin{cases} \max_{i=l-1}^r (f_{l,i,k-1,0} + f_{i + 1,r, k-1,1}+\sum_{j=i+1}^r v_j) & \lfloor \frac{m}{2^k} \rfloor \; \text{is odd} \\ f_{l,r,k-1,1} & \mathrm{otherwise} \end{cases} \end{aligned} \]显然：
\[Answer = f_{1,n,\lfloor \log{V} \rfloor,1} \]时间复杂度 \(O(n^3\log{m})\) 。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18, lim = 1e16;
int n, m, v[205], f[205][205][70][2];
signed main (){
scanf ("%lld%lld", &n, &m);
for (int i = 1;i <= n;++ i)
scanf ("%lld", &v[i]);
int k;
for (k = 0;(1ll << k) <= m;++ k)
for (int l = 1;l <= n;++ l)
for (int r = l;r <= n;++ r)
if (k == 0){
if (r - l < 1){
f[l][r][k][0] = max (0ll, v[l]);
f[l][r][k][1] = v[l] * (m & 1);
} else
if (r - l < 2){
f[l][r][k][0] = v[r];
if (m & 1)
f[l][r][k][1] = v[r];
else
f[l][r][k][1] = - inf;
} else
f[l][r][k][0] = f[l][r][k][1] = - inf;
} else {
f[l][r][k][0] = f[l][r][k][1] = - inf;
for (int i = r, Sum = 0;i >= l - 1;-- i){
f[l][r][k][0] = max (f[l][r][k][0], f[l][i][k - 1][0] + f[i + 1][r][k - 1][0] + Sum);
Sum += v[i];
}
if (m >> k & 1)
for (int i = r, Sum = 0;i >= l - 1;-- i){
f[l][r][k][1] = max (f[l][r][k][1], f[l][i][k - 1][0] + f[i + 1][r][k - 1][1] + Sum);
Sum += v[i];
}
else
f[l][r][k][1] = f[l][r][k - 1][1];
}
printf ("%lld\n", f[1][n][k - 1][1]);
return 0;
}
似乎提交时需要吸氧。
例2 -CF1290F Making Shapes
“Codeforces *3500 的简单题罢了。”
题面
给定 \(n\) 个向量，满足任意两个向量不共线。你需要按照如下方式画图：
- 初始点在 \((0,0)\)
- 选择一个向量，从当前点连向当前点加上这个向量得到的点
- 重复第二个操作，最后回到 \((0,0)\) 并停止。
这样你可以得到一个多边形，问有多少种画法使得得到一个凸多边形且最终的多边形可以被放到 \(m\times m\) 的矩形里。输出答案对 \(998244353\) 取模。
\(n \le 5, m \le 10^9 , |x_i|,|y_i| \le 4\)
放上 zjk 口头简化的题意（由凸包的性质显然）：
给定 \(n\) 个向量 \((x_i,y_i)\) 和 \(m\) ，求有多少组非负的 \(a_1,\cdots,a_n\) 满足以下所有条件：
\[\begin{aligned} & \sum a_ix_i=0 \\ & \sum a_iy_i=0 \\ & \sum_{x_i>0} a_ix_i \leq m \\ & \sum_{y_i>0} a_iy_i \leq m & \end{aligned} \]答案对 \(998244353\) 取模。
思路
直接跳过
不想解释其他更多了。考虑数位 DP。由低到高确定 \(c_i\) 的每一位的值。
记
\[f_{d,px,py,nx,ny,xs,ys} \]含义
\(d\) ：当前确定了低 \(d\) 位。
\(px\) ：低 \(d\) 位的 \(\sum_{x_i>0}x_i\) 产生的进位。
\(py\) ：低 \(d\) 位的 \(\sum_{y_i>0}y_i\) 产生的进位。
\(nx\) ：低 \(d\) 位的 \(\sum_{x_i<0}(-x_i)\) 产生的进位。
\(ny\) ：低 \(d\) 位的 \(\sum_{y_i<0}(-y_i)\) 产生的进位。
\(xs(0/1)\) ：\(\sum_{x_i>0}c_ix_i\) 的低 \(d\) 位是否小于等于 \(m\) 的低 \(d\) 位。
\(ys(0/1)\) ：\(\sum_{y_i>0}c_iy_i\) 的低 \(d\) 位是否小于等于 \(m\) 的低 \(d\) 位。
转移
枚举 \(n\) 个 \(c_i\) 的第 \(d+1\) 位的值（\(0/1\)）。
具体实现见代码。
Code
#include <bits/stdc++.h>
using namespace std;
#define spl (1 << n)
const int N = 5, mod = 998244353;
const int M = N << 2;
const int S = 1 << N;
int n, m, x[N], y[N];
int f[32][M][M][M][M][2][2];
int Px[S], Py[S], Nx[S], Ny[S];
int PX, PY, NX, NY, A, B;
void Mod (int &a){
a -= mod;
a += a >> 31 & mod;
}
int main (){
scanf ("%d%d", &n, &m);
for (int i = 0;i < n;++ i)
scanf ("%d%d", &x[i], &y[i]);
f[0][0][0][0][0][0][0] = 1;
for (int i = 0;i < spl;++ i)
for (int j = 0;j < n;++ j)
if (i >> j & 1){
if (x[j] > 0)
Px[i] += abs (x[j]);
else
Nx[i] += abs (x[j]);
if (y[j] > 0)
Py[i] += abs (y[j]);
else
Ny[i] += abs (y[j]);
}
for (int d = 0;d <= 30;++ d)
for (int px = 0;px <= Px[spl - 1];++ px)
for (int py = 0;py <= Py[spl - 1];++ py)
for (int nx = 0;nx <= Nx[spl - 1];++ nx)
for (int ny = 0;ny <= Ny[spl - 1];++ ny)
for (int a = 0;a < 2;++ a)
for (int b = 0;b < 2;++ b)
for (int s = 0;s < spl;++ s)
if (! ((px + Px[s] + nx + Nx[s]) & 1) && ! ((py + Py[s] + ny + Ny[s]) & 1)){
PX = (px + Px[s]) >> 1;
PY = (py + Py[s]) >> 1;
NX = (nx + Nx[s]) >> 1;
NY = (ny + Ny[s]) >> 1;
A = (a + ((px + Px[s]) & 1)) > (m >> d & 1);
B = (b + ((py + Py[s]) & 1)) > (m >> d & 1);
Mod (f[d + 1][PX][PY][NX][NY][A][B] += f[d][px][py][nx][ny][a][b]);
}
Mod (f[31][0][0][0][0][0][0] += mod - 1);
printf ("%d\n", f[31][0][0][0][0][0][0]);
return 0;
}
子集 DP
似乎就是状态压缩 DP ？
（zjk 对于子集 DP似乎一笔带过惹）
轮廓线 DP（鸽）
先鸽吧。类似插头 DP。具体题目具体分析。（场上遇到再想吧）
DP 的组合意义
“部分情况下，DP 的系数具有很好的组合意义。此时可以通过加入一些状态，使用这些状态的转移凑出 DP 的系数。” ——zjk
感觉通俗地说，就是将原本的一种转移思路拆成一些组合意义，最后再进行组合，求出答案。
例1
题面
给一棵 \(n\) 个点的树。显然有 \(2^{n-1}\) 种删边的方式（不考虑顺序）。对所有的方式求和：每个连通块的大小的乘积。
思路
显然可以有 \(O(n^2)\) 的（暴力）DP。
考虑转化原题。相当于划分连通块，在每个连通块中选一个代表点，总共的方案数。
这时显然有一种思路考虑 \(u\) 子树内 \(u\) 所在的连通块是否已经选出代表点的，记录分别的方案数为 \(f_{u,0}\) （否），\(f_{u,1}\) （是）。
于是有：
\[\begin{aligned} & \text{init: } \forall u, son_u = \empty : f_{u,0} = f_{u,1}=1\\ & f_{u,0} = \prod_{v \in son_u} (f_{v,0} + f_{v,1}) \\ & f_{u,1} = \prod_{v \in son_u} (f_{v,0} + f_{v,1}) + \sum_{v \in son_u}(f_{v,1} \prod_{v' \in son_u,v' \neq v} f_{v',0}) \end{aligned} \]显然，答案可知：
\[Answer=f_{root,1} \]复杂度 \(O (n)\)。
常见的组合意义
- 一个大小为 \(n\) 的集合权值为 \(a^n\)，等价于每选一个数乘上 \(a\) 的权值。
- 一个大小为 \(n\) 的集合权值为 \(n\)，等价于在集合中选一个数。
- 一个大小为 \(n\) 的集合权值为 \(\tbinom{n}{k}\)，等价于选出 \(k\) 个不同的数。
- 一个大小为 \(n\) 的集合权值为 \(n^k\)，等价于 \(\sum_{i=0}^{k} {k \brace i} n^{\underline{i}}\) ，等价于 \(\sum_{i=0}^k{k \brace i} (i! )\tbinom{n}{i}\)。其中 \({k \brace i}\) 为 第二类斯特林数。其公式有三：
例2 - [ARC124E] Pass to Next
题面
一个环上有 \(n\) 个人，初始第 \(i\) 个人有 \(a_i\) 个球。
所有人同时进行如下操作：拿出自己球的一部分，扔给下一个人。设操作结束后第 \(i\) 个人有 \(b_i\) 个球。
对于所有可能得到的序列 \(\{b_i\}\)，求和： \(\prod b_i\)。
答案对 \(998244353\) 取模。
\(n \leq 10^5\)
思路
考虑对 \(b_i\) 去重的操作。显然只要钦定最少有一个人不扔球，统计时就不会重复。
再考虑将 \(\prod b_i\) 变为在这些球中选一个，方便 DP。
于是为了使最少有一个人不扔球，考虑容斥。计算出 \(\forall i : b_i \in [0,a_i]\) 的答案数，减去 \(\forall i : b_i \in [1,a_i]\) 的答案数，就是答案。
发现实际上后者的值就是建立在前者上的，所以考虑做两次 DP，第二次时对 \(a_i\) 进行一些操作，再计算答案。
考虑将 \(\prod b_i\) 转化成在每个操作完的 \(b_i'\) 中选择一个数。
于是我们开始考虑 DP ，记 \(f_{i,0}\) 表示第 \(i\) 个人选原有的球，他前面的 \(i - 1\) 个人的答案；\(f_{i,1}\) 表示第 \(i\) 个人选传过来的球，他前面（包括他自己）\(i\) 个人的答案。
考虑转移，设第一个人的状态为 \(u = 0/1\)，表示选择传过来的或者自己的（\(\oplus\) 表示异或），再记录 \(upd = 0/-1\) 表示是（\(0\)）否（\(- 1\)）考虑 \(0\) ：
\[\begin{aligned} & \text{init: }\forall i \neq 1 : f_{i,0} = f_{i, 1} = 0 \\ & \text{init: }f_{1,u} = 1 , f_{1,u \oplus 1} = 0 \\ & \text{init: }\forall i, j:s_i(j) = \sum_{k = 1}^j k^i \\ & f_{i+1,0} \mathop{\leftarrow} \limits^+ f_{i,0}s_1(a_i + upd) + f_{i,1}(a_i + upd + 1) \\ & f_{i+1,1} \mathop{\leftarrow} \limits^+ f_{i,0}(a_is_1(a_i) - s_2(a_i))+f_{i,1}s_1(a_i) \end{aligned} \]相当于分四种情况 \(0/1 \to 0/1\) 讨论，系数显然。特别说明，转移 \(f_{i+1,1}\) 时，因为一定要传，与 \(upd\) 无关，所以 \(a_i\) 不需要加上 \(upd\)。
显然答案为：
\[Answer = \begin{cases} f_{n+1,0} & f_{1,0} = 1 \\ f_{n+1,1} & \mathrm{otherwise} \end{cases} \]复杂度 \(O(n)\)，可以轻松通过。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n, a[100005], f[100005][2];
int Qpow (int a, int p){
int Res = 1;
while (p > 0){
if (p & 1)
Res = Res * a % mod;
a = a * a % mod;
p >>= 1;
}
return Res;
}
int inv (int i){
return Qpow (i, mod - 2);
}
int S1 (int k){
return k * (k + 1) % mod * inv (2) % mod;
}
int S2 (int k){
return k * (k + 1) % mod * ((k << 1) + 1) % mod * inv (6) % mod;
}
int Solve (int init, int upd){
f[1][init] = 1;
f[1][init ^ 1] = 0;
for (int i = 1;i <= n;++ i)
f[i + 1][0] = f[i + 1][1] = 0;
for (int i = 1;i <= n;++ i){
f[i + 1][0] += S1 (a[i] + upd) * f[i][0] % mod + (a[i] + upd + 1) * f[i][1] % mod;
f[i + 1][0] %= mod;
f[i + 1][1] += ((a[i]) % mod * S1 (a[i]) % mod - S2 (a[i]) + mod) % mod * f[i][0] + S1 (a[i]) % mod * f[i][1];
f[i + 1][1] %= mod;
}
return f[n + 1][init];
}
signed main (){
scanf ("%lld", &n);
for (int i = 1;i <= n;++ i)
scanf ("%lld", &a[i]);
printf ("%lld\n", ((Solve (1, 0) + Solve (0, 0)) % mod - (Solve (1, - 1) + Solve (0, - 1)) % mod + mod) % mod);
return 0;
}
例3 - [AGC001E] BBQ Hard
题面
有 n 个数对 \((a_i,b_i)\)，求出：
\[\sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j} \]答案对 \(10^9 + 7\) 取模。
\(n \leq 2 \times 10^5,a_i \leq 2 \times 10^3,b_i \leq 2 \times 10^3\)
思路
已知 \(\tbinom{a+b}{a}\) 等价于从 \((0,0)\) 到 \((a,b)\) 只能向上或向右走的方案数。
所以 \({a_i+b_i+a_j+b_j \choose a_i+a_j}\) 等价于从 \((-a_i,-b_i)\) 走到 \((a_j, b_j)\) 只能向上或向右走的方案数。
然后就很 easy 了，考虑在平面上 DP，然后去掉 \(i \to i\) 的答案，再除以 \(2\)。（注意到只能从编号小的走到编号大的）
方程过于简单，这里不写了。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, a[200005], b[200005], A[200005], B[200005], f[4050][4050];
int jc[8005], inj[8005], inv[8005], Ans;
int C (int i, int j){
return jc[i] * inj[j] % mod * inj[i - j] % mod;
}
signed main (){
jc[0] = jc[1] = 1;
inj[0] = inj[1] = 1;
inv[1] = 1;
for (int i = 2;i <= 8001;++ i){
inv[i] = inv[i - mod % i] * (mod / i + 1) % mod;
jc[i] = jc[i - 1] * i % mod;
inj[i] = inj[i - 1] * inv[i] % mod;
}
scanf ("%lld", &n);
for (int i = 1;i <= n;++ i){
scanf ("%lld%lld", &a[i], &b[i]);
A[i] = 2010 - a[i];
B[i] = 2010 - b[i];
++ f[A[i]][B[i]];
}
for (int i = 1;i <= 4020;++ i)
for (int j = 1;j <= 4020;++ j)
f[i][j] = (f[i][j] + f[i - 1][j] + f[i][j - 1]) % mod;
for (int i = 1;i <= n;++ i){
Ans = (Ans + f[a[i] + 2010][b[i] + 2010]) % mod;
Ans = (Ans - C ((a[i] + b[i]) << 1, a[i] + a[i]) + mod) % mod;
}
printf ("%lld\n", Ans * inv[2] % mod);
return 0;
}
综合练习 - UOJ667 提问系统
题面
给一个栈，有 \(2n\) 个操作，每个操作为以下两种类型之：
- 向栈中加入一个元素。
- 弹出栈顶元素。
操作类型已知，且保证最后栈为空。
在每次加入元素时，你需要选择将其染成红色或者蓝色。
有一个限制：任意时刻栈中红色元素数量不超过 \(l_0\) ，蓝色元素数量不超过 \(l_1\)。
对于所有合法的染色方案，记 \(c_0\) 表示染红色的次数， \(c_1\) 表示染蓝色的次数，求和 \(c_0c_1^2\)。
\(n \leq 2500\)
思路
加入、弹出元素的操作可以看作一棵树的结构：入栈就是在当前节点加一个儿子；出栈就是往父节点走；任意时刻栈中的元素集合的集合与树上点到根形成的链上点集的集合构成双射（吧）。
问题变成给一棵 \(n + 1\) 个点（算上空节点）的有根树，限制变为任意一条点到根的路径上红蓝点数量分别不超过 \(l_0,l_1\)。
注意到：
\[c_0c_1^2 = 2{c_0 \choose 1}{c_1 \choose 2} + {c_0 \choose1}{c_1 \choose 1} \]右式的左部相当于 \(2\) 倍的“从红色点中选 \(1\) 个，从蓝色点中选 \(2\) 个”的方案数；右部相当于“从红色点中选 \(1\) 个，从蓝色点中选 \(1\) 个”的方案数。
在染色之后考虑小容量背包 DP 解决。
直接记录子树内的情况显然是过不去的。所以考虑 \(f_{u, t_0, t_1}\) 再加上一坨 \(0/1/2\) 后缀表示从 \(u\) 到根的链上有 \(t_0\) 个红色点，\(t_1\) 个蓝色点，\(u\) 子树内的合法状态，转移比较显然。这样设计的状态表面上有 \(O(n^3)\) 的复杂度，实际上由于 \(t_0+t_1=dep_u\) 即 \(u\) 的深度，所以实际上复杂度 \(O(n^2)\)，转移 \(O(1)\)，所以总时间复杂度为 \(O(n^2)\)，当然由于我们算的方案数的要求，实际的常数约在 \(10\) 到 \(20\) 的范围内。
具体的转移有些复杂，就不写了，看代码吧。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n, c0, c1, cnt;
char opt[5];
int firs[5005], nex[5005], to[5005], tot, fa[5005];
int dep[5005], f[2505][2505][2][3], cs[2][3];
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
void Init (int u){
for (int e = firs[u];e;e = nex[e]){
int v = to[e];
dep[v] = dep[u] + 1;
Init (v);
}
}
void Solve (int u, int x, int y){
for (int e = firs[u];e;e = nex[e])
Solve (to[e], x, y);
int r0, r1;
for (int t0 = 0, t1 = dep[u];t1 >= 0;++ t0, -- t1){
if (t0 > c0 || t1 > c1)
continue;
r0 = t0;
r1 = t1;
// choose red
if (r0 < c0){
++ r0;
for (int i = 0;i <= x;++ i)
for (int j = 0;j <= y;++ j)
cs[i][j] = 0;
cs[0][0] = cs[1][0] = 1;
for (int e = firs[u];e;e = nex[e]){
int v = to[e];
for (int p = x;p >= 0;-- p)
for (int q = y;q >= 0;-- q){
int Res = 0;
for (int i = 0;i <= p;++ i)
for (int j = 0;j <= q;++ j)
Res = (Res + cs[p - i][q - j] * f[v][r0][i][j] % mod) % mod;
cs[p][q] = Res;
}
}
for (int p = 0;p <= x;++ p)
for (int q = 0;q <= y;++ q)
f[u][t0][p][q] = (f[u][t0][p][q] + cs[p][q]) % mod;
-- r0;
}
//choose blue
if (r1 < c1){
for (int i = 0;i <= x;++ i)
for (int j = 0;j <= y;++ j)
cs[i][j] = 0;
cs[0][0] = cs[0][1] = 1;
for (int e = firs[u];e;e = nex[e]){
int v = to[e];
for (int p = x;p >= 0;-- p)
for (int q = y;q >= 0;-- q){
int Res = 0;
for (int i = 0;i <= p;++ i)
for (int j = 0;j <= q;++ j)
Res = (Res + cs[p - i][q - j] * f[v][r0][i][j] % mod) % mod;
cs[p][q] = Res;
}
}
for (int p = 0;p <= x;++ p)
for (int q = 0;q <= y;++ q)
f[u][t0][p][q] = (f[u][t0][p][q] + cs[p][q]) % mod;
}
}
}
void Main_Solve (int r, int x, int y){
for (int i = 0;i <= x;++ i)
for (int j = 0;j <= y;++ j)
f[r][0][i][j] = 0;
f[r][0][0][0] = 1;
for (int e = firs[r];e;e = nex[e]){
int v = to[e];
Solve (v, x, y);
for (int p = x;p >= 0;-- p)
for (int q = y;q >= 0;-- q){
int Res = 0;
for (int i = 0;i <= p;++ i)
for (int j = 0;j <= q;++ j)
Res = (Res + f[r][0][p - i][q - j] * f[v][0][i][j] % mod) % mod;
f[r][0][p][q] = Res;
}
}
}
signed main (){
cnt = 1;
scanf ("%lld%lld%lld", &n, &c0, &c1);
for (int i = 1, p = 1;i <= (n << 1);++ i){
scanf ("\n%s", opt);
if (opt[1] == 'u'){
++ cnt;
Add (p, cnt);
fa[cnt] = p;
p = cnt;
}
else {
p = fa[p];
}
}
dep[1] = - 1;
Init (1);
Main_Solve (1, 1, 2);
printf ("%lld\n", (f[1][0][1][1] + (f[1][0][1][2] << 1) % mod) % mod);
return 0;
}
实际上只跑了 214ms，超级快。
DP of DP （DP 套 DP）
DP 套 DP主要解决一些字符串相关的问题，是一个小技巧。
总结下来就是将一个 DP 整个压入另一个 DP 的状态中。
通常要进行精细的状态设计，甚至猜测状态数很小。
例1 [TJOI2018] 游园会/Party
题面
给定 \(n\) 和长度为 \(m\) 的序列 \(t\) ，对于每个 \(k\) 求所有长度为 \(n\) 的序列 \(a\) 中有多少个序列和 \(t\) 的 LCS 为 \(k\)。
特别地，\(a\) 中不允许出现 "NOI" 子串。
\(n \leq 10^3,m \leq 15\)，字符集大小为 \(3\)（N,O,I）
思路
考虑将正常求两个序列最长 LCS 的 DP 进行一些魔幻的转化。
发现 \(m\) 极小，同时发现上面的 DP 方程中 \(g_{i,j} - g_{i,j-1} \leq 1\) 的显然（但是很难发现）的性质。
于是考虑状压 \(j\) 位上的 DP 值，考虑差分后变为 \(0/1\) 串，直接状压。
考虑 \(f_{i,j,k}\) 表示考虑长度为 \(i\) 的字符串前缀（来自 \(a\)），处在 \(j\) 的状态上，以及匹配 "NOI" 的长度是 \(k\) 时符合上述所有条件的字符串个数。
然后无脑 DP，记得开滚动数组。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define le (1 << m)
const int mod = 1e9 + 7;
int n, m, Ans[20];
int f[2][1 << 15][3], xa[20], xb[20], cs[35000];
char s[20];
int W (int i){
return i & 1;
}
int R (int i){
return W (i) ^ 1;
}
int Upload (){
int Res = 0;
for (int i = 0;i < m;++ i)
Res |= xb[i + 1] - xb[i] << i;
return Res;
}
void Download (int p){
for (int i = 0;i < m;++ i)
xa[i + 1] = (p >> i) & 1;
for (int i = 1;i <= m;++ i)
xa[i] += xa[i - 1];
}
void Update (int u, int sit, int np, char c, int cos){
Download (sit);
for (int i = 1;i <= m;++ i)
xb[i] = max (max (xb[i - 1], xa[i]), xa[i - 1] + (int) (c == s[i]));
(f[R (u)][Upload ()][np] += cos % mod) %= mod;
}
signed main (){
scanf ("%lld%lld\n%s", &n, &m, s + 1);
for (int i = 1;i <= 32767;++ i)
cs[i] = cs[i >> 1] + (i & 1);
f[0][0][0] = 1;
for (int i = 0;i < n;++ i){
for (int j = 0;j < le;++ j)
for (int p = 0;p < 3;++ p)
f[R (i)][j][p] = 0;
for (int j = 0;j < le;++ j){
if (f[W (i)][j][0] > 0){
Update (W (i), j, 1, 'N', f[W (i)][j][0]);
Update (W (i), j, 0, 'O', f[W (i)][j][0]);
Update (W (i), j, 0, 'I', f[W (i)][j][0]);
}
if (f[W (i)][j][1] > 0){
Update (W (i), j, 1, 'N', f[W (i)][j][1]);
Update (W (i), j, 2, 'O', f[W (i)][j][1]);
Update (W (i), j, 0, 'I', f[W (i)][j][1]);
}
if (f[W (i)][j][2] > 0){
Update (W (i), j, 1, 'N', f[W (i)][j][2]);
Update (W (i), j, 0, 'O', f[W (i)][j][2]);
}
}
}
for (int i = 0;i < le;++ i)
for (int p = 0;p < 3;++ p)
Ans[cs[i]] = (Ans[cs[i]] + f[W (n)][i][p]) % mod;
for (int i = 0;i <= m;++ i)
printf ("%lld\n", Ans[i]);
return 0;
}
例2 CF578D LCS Again
题面
给定一个长度为 \(n\) 字符串 \(S\)，字符集大小为 \(m\)，求有多少个与 \(S\) 等长字符串 \(T\)，满足 \(\mathrm{LCS}(S,T)=|S|-1\)，其中 \(S,T\) 只包含前 \(m\) 个小写字母。
\(n \leq 10^5\)
思路
考虑 DP 套 DP。我们发现因为有 \(\mathrm{LCS}(S,T)=|S|-1\) 的要求，所以无论如何在用内层 DP 求 LCS 时一定会经过 \(f_{i,i - 1}\) 或 \(f_{i,i}\) 或 \(f_{i,i + 1}\) 这三个位置。
进一步考虑，一定只有这些情况可以转移出 \(\geq n - 1\) 的 LCS 长度：
\[\begin{aligned} & f_{i,i - 1} = \{i - 2,i - 1\} \\ & f_{i,i} = \{i - 1, i\} \\ & f_{i,i + 1} = \{i-1,i\} \\ \end{aligned} \]所以我们考虑记录这些状态是否出现的 \(0/1\) 串，就可以愉快地 DP 了。
设 \(f_{i,0/1,0/1,0/1}\) 表示选到 \(T\) 的长度为 \(i\) 的前缀，上述状态的值为前者还是后者（显然如果都不是则不考虑）。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, f[100005][8];
int r[5], w[5], c[100005];
char s[100005];
signed main (){
scanf ("%lld%lld\n%s", &n, &m, s + 1);
for (int i = 1;i <= n;++ i)
c[i] = s[i] - 'a';
for (int i = 0;i < m;++ i){
int sit = 1;
if (i == c[1])
sit |= 2;
if (i == c[1] || i == c[2])
sit |= 4;
++ f[1][sit];
}
for (int i = 1;i < n;++ i){
for (int j = 0;j < 8;++ j){
r[0] = i - 2 + (j & 1);
r[1] = i - 1 + (j >> 1 & 1);
r[2] = i - 1 + (j >> 2 & 1);
for (int k = 0;k < m;++ k){
w[0] = max (r[1], r[0] + (k == c[i]));
w[1] = max (max (r[2], w[0]), r[1] + (k == c[i + 1]));
w[2] = max (w[1], r[2] + (k == c[i + 2]));
if (w[0] < i - 1 || w[1] < i || w[2] < i)
continue;
int sit = 0;
sit |= (w[0] - (i - 1));
sit |= (w[1] - (i)) << 1;
sit |= (w[2] - (i)) << 2;
f[i + 1][sit] += f[i][j];
}
}
}
printf ("%lld\n", f[n][0] + f[n][1] + f[n][4] + f[n][5]);
return 0;
}
小练习
- loj#3669
- loj#3042
- loj#3848
值域与分界点（鸽）
hh，不会（悲）。
杂项
DP 中记录关键状态
保留部分 DP 的关键状态完成转移，因此可以只转移关键的状态，如分界点。
更多的体现：例如，两个人在数轴上移动接球，在没有球落下时状态是二维的，但在有一个球落下的时刻可能的状态只剩下了一维，因此常见的做法是只对有球落下的时刻 DP。
我们要考虑的是如何选择要记录的信息。更进一步地说，如何选出尽量少，但又足够处理转移的信息有时也需要仔细分析。
DP 的顺序
这也经常是一个需要考虑的问题。就像树上的 DP 顺序选择一样，合理的 DP 的顺序选择通常会使看似不可做的题变得十分简单而可做了。
例1 loj#2743./luoguP9197 [JOI Open 2016] 「高層ビル街/Skyscraper/摩天大楼」
题面
给几个长度为 \(n\) 的序列 \(v\)，求有多少种排列序列的方式使得 \(\sum_{i=1}^{n-1} |v_i - v_{i+1}| \leq L\)。
\(n \leq 10^2,L \leq 10^3\)
思路
听说有种东西叫做连续段 DP？（感觉好高级）但是其实就是选择 DP 顺序的一个很经典的例子。考虑换一种顺序进行 DP。
令 \(S=\sum_{i=1}^{n-1} |v_i - v_{i+1}|\)。
考虑将 \(v\) 从大到小排序，然后尝试放入序列中。每次可以把当前的数插入原序列中，考虑手动划分出一些折线段（请结合自己的手绘图像）。显然每次把 \(v_i\) 的状态推向 \(v_{i+1}\) 的话，对于每不是最左右段的某一段的两个端点一定会连向 \(\leq v_{i+1}\) 的某个点，所以这一段对 \(S\) 的贡献为 \(2(v_{i+1} - v_i)\)。当然因为最左段或者最右段的特殊性，我们可以在 DP 的状态中钦定当前的最左段的左端点能否再延伸，最右端同理。当然最左段的右端和最右段的左端可以正常延伸和转移。
具体地，定义 \(f_{t,i,l,0/1,0/1}\) 表示放入前 \(t\) 大的数，当前划分了 \(i\) 段，已经知道的对 \(S\) 的贡献为 \(l\)，左段的左端点是否能延伸，右段的右端点是否能延伸。
转移式如下：
\[\begin{aligned} & \text{init: } \forall p \in \{0,1\},q \in \{0,1\}:f_{1,1,0,p,q} \leftarrow 1 \\ & \text{let: } x \leftarrow l + (2i - p - q)(v_t-v_{t+1}) \\ & \text{let: } w \leftarrow f_{t,i,x,p,q} \\ & \text{Part of creating a new segment:} \\ & \;\;\;\; f_{t+1,i+1,x,p,q} \mathop{\leftarrow} \limits^+ (i-1)w & i > 1 \\ & \;\;\;\; f_{t+1,i+1,x,0,q} , f_{t+1,i+1,x,1,q} \mathop{\leftarrow} \limits^+ w & p = 0 \\ & \;\;\;\; f_{t+1,i+1,x,p,0} , f_{t+1,i+1,x,p,1} \mathop{\leftarrow} \limits^+ w & q = 0 \\ & \text{Part of extending a original segment:} \\ & \;\;\;\; f_{t+1,i,x,p,q} \mathop{\leftarrow} \limits^+ 2(i-1)w & i > 1 \\ & \;\;\;\; f_{t+1,i,x,0,q} , f_{t+1,i,x,1,q} \mathop{\leftarrow} \limits^+ w & p = 0 \\ & \;\;\;\; f_{t+1,i,x,p,0} , f_{t+1,i,x,p,1} \mathop{\leftarrow} \limits^+ w & q = 0 \\ & \text{Part of merging two original segments into one by using } v_{t+1} : \\ & \;\;\;\; f_{t+1,i-1,x,p,q} \mathop{\leftarrow} \limits^+ (i-1)w & i > 1 \end{aligned} \]稍稍有一点冗长，但是其实很好理解的，其实就是分类讨论左段（就是 \(q = 0\) 的情况）、右段（就是 \(p=0\) 的情况）、中间（就是 \(i>1\) 的情况）进行计算。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, L, a[105], f[2][105][1005][2][2], Ans;
bool cmp (int i, int j){
return i > j;
}
int w (int i){
return i & 1;
}
int r (int i){
return w (i) ^ 1;
}
signed main (){
scanf ("%lld%lld", &n, &L);
for (int i = 1;i <= n;++ i)
scanf ("%lld", &a[i]);
for (int i = 0;i < 2;++ i)
for (int j = 0;j < 2;++ j)
f[1][1][0][i][j] = 1;
sort (a + 1, a + n + 1, cmp);
for (int g = 1;g < n;++ g){
for (int i = 1;i <= g + 1;++ i)
for (int l = 0;l <= L;++ l)
for (int p = 0;p < 2;++ p)
for (int q = 0;q <= 2;++ q)
f[r (g)][i][l][p][q] = 0;
for (int i = 1;i <= g;++ i)
for (int l = 0;l <= L;++ l)
for (int p = 0;p < 2;++ p)
for (int q = 0;q < 2;++ q){
if (f[w (g)][i][l][p][q] < 1)
continue;
int x = l + (2 * i - p - q) * (a[g] - a[g + 1]);
if (x > L)
continue;
// Creat
if (i > 1)
(f[r (g)][i + 1][x][p][q] += f[w (g)][i][l][p][q] * (i - 1) % mod) %= mod;
if (p < 1){
(f[r (g)][i + 1][x][0][q] += f[w (g)][i][l][p][q]) %= mod;
(f[r (g)][i + 1][x][1][q] += f[w (g)][i][l][p][q]) %= mod;
}
if (q < 1){
(f[r (g)][i + 1][x][p][0] += f[w (g)][i][l][p][q]) %= mod;
(f[r (g)][i + 1][x][p][1] += f[w (g)][i][l][p][q]) %= mod;
}
// Extend
if (i > 1)
(f[r (g)][i][x][p][q] += (i - 1 << 1) * f[w (g)][i][l][p][q] % mod) %= mod;
if (p < 1){
(f[r (g)][i][x][0][q] += f[w (g)][i][l][p][q]) %= mod;
(f[r (g)][i][x][1][q] += f[w (g)][i][l][p][q]) %= mod;
}
if (q < 1){
(f[r (g)][i][x][p][0] += f[w (g)][i][l][p][q]) %= mod;
(f[r (g)][i][x][p][1] += f[w (g)][i][l][p][q]) %= mod;
}
// Merge
if (i > 1)
(f[r (g)][i - 1][x][p][q] += (i - 1) * f[w (g)][i][l][p][q] % mod) %= mod;
}
}
for (int i = 0;i <= L;++ i)
(Ans += f[w (n)][1][i][1][1]) %= mod;
printf ("%lld\n", Ans);
return 0;
}
DP 前对题目的性质分析
在遇到一些感觉不能 DP 的题目，可以尝试分析性质。
例1 loj#3037./luoguAT_joisc2019_h「ランプ/Lamps」
译自 JOISC 2019 Day3 T2「ランプ / Lamps」
走廊上有排成一列的 \(n\) 盏灯，给出了一个 \(01\) 串 \(S\) 表示其开关状态（\(1\) 表示打开，\(0\) 表示关闭）。现在想要把这 \(n\) 盏灯变成目标状态 \(T\)。
你有三种操作：
- OFF 操作：选择一个区间，将区间内所有的灯关闭。
- ON 操作：选择一个区间，将区间内所有的灯打开。
- TOG 操作：选择一个区间，在区间内关闭原本打开的灯，打开原本关闭的灯。
求将灯的状态从 \(S\) 变为 \(T\) 的最小的操作数。
思路
hhh，仔细想明白性质就是简单题了。
首先其实只有两种操作，区间赋值和区间异或 \(1\)，分类讨论会发现，如果我们先做一次区间异或再做一次区间赋值，一定可以转化成先做一次区间赋值再做一次区间异或。另外通过分类讨论同样可知区间赋值包含或有交的情况一定可以通过删除或加上异或操作后的变形成为无交的区间赋值；同样区间异或也无交。然后就很好做了。
记 \(f_{i,0/1/2,0/1}\) 表示考虑前 \(i\) 个灯，在 \(i\) 这个位置做的赋值的信息（\(0:\) 赋值为 \(0\)；\(1:\) 赋值为 \(1\)；\(2:\) 不赋值），在 \(i\) 这个位置做的异或的信息（\(0:\) 不操作；\(1:\) 操作）。呃，有人说还有存 \(0/1\) 串奇偶性之类的。。不是很清楚，但我这样做是对的。
特别地记 \([\;]\) 为艾弗森括号，转移式如下：
\[\begin{aligned} & \text{init: } f_{0,2,0} = 0 \\ & \text{init: } \forall i,j,k,i\neq 0 \lor j\neq 2 \lor k\neq 0:f_{i,j,k} =inf \\ & \text{let: } k \leftarrow [j \neq t_i] \\ & f_{i,j,k} \mathop{\leftarrow} \limits^{\min} f_{i-1,p,q} + [j \neq p] + [k > 0 \land q = 0] & j < 2 \land p < 3 \land q < 2 \\ & f_{i,j,[s_i \neq t_i]} \mathop{\leftarrow} \limits^{\min} f_{i-1,p,q} + [s_i \neq t_i \land q \neq 0] & j=2\land p < 3 \land q <2 \end{aligned} \]答案为：
\[Answer=\sum_{i=0}^2\sum_{j=0}^1f_{n,i,j} \]Code
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, Ans = inf;
int a[1000005], b[1000005], f[1000005][3][2];
char c[1000005];
void Update (int &a, int b){
a = min (a, b);
}
int main (){
scanf ("%d", &n);
scanf ("\n%s", c + 1);
for (int i = 1;i <= n;++ i)
if (c[i] == '1')
a[i] = 1;
scanf ("\n%s", c + 1);
for (int i = 1;i <= n;++ i)
if (c[i] == '1')
b[i] = 1;
for (int i = 0;i <= n;++ i)
for (int j = 0;j < 3;++ j)
for (int k = 0;k < 2;++ k)
f[i][j][k] = inf;
f[0][2][0] = 0;
for (int i = 1;i <= n;++ i){
int k;
for (int j = 0;j < 2;++ j){
k = (int) (j != b[i]);
for (int p = 0;p < 3;++ p)
for (int q = 0;q < 2;++ q)
Update (f[i][j][k], f[i - 1][p][q] + (int) (j != p) + (int) (k && ! q));
}
k = (int) (a[i] != b[i]);
for (int p = 0;p < 3;++ p)
for (int q = 0;q < 2;++ q)
Update (f[i][2][k], f[i - 1][p][q] + (int) (k && ! q));
}
for (int i = 0;i < 3;++ i)
for (int j = 0;j < 2;++ j)
Update (Ans, f[n][i][j]);
printf ("%d\n", Ans);
return 0;
}