【例题 1】单调栈自动机
引自 https://www.luogu.com.cn/blog/EternalAlexander/pu-ji-zu-zhuan-ti-sui-bi-1dp-of-dp。
对于一个数，你可以进行任意次操作，每次操作可以删去数字相同的连续一段，例如你可以把 \(1122331\) 变成 \(22331\)，\(11331\)，\(11221\) 或者 \(112233\)。当然，如果整个数都是连续的一段，那么我们可以将它变成 \(0\)。
记把 \(i\) 变成 \(0\) 的最少操作次数是 \(f(i)\)，给出 \(k,l,r\)，求 \(l\) 到 \(r\) 内的数有多少满足 \(f(i)=k\)。
\(1\le l\le r\le10^{18}\)。
求 \(f(i)\) 是显然的。维护一个单调栈，从左往右扫，把遇到的数字入栈时，将栈中大于自己的数都弹掉，并且使 \(ans\) \(+1\)，然后如果等于自己就合并起来（就是删掉当前插入的这个），小于则插入。
然后怎么计数呢？写在题面上的让你数位 dp。我们考虑把单调栈的状态压进 dp 的状态。设 \(f_{i,j,S,0/1}\) 表示考虑到第 \(i\) 位，前面已经消耗的代价为 \(j\)，当前单调栈中的元素为 \(S\)（一个集合），并且已经/没有达到数位限制的方案数。这样就可以按套路数位 dp 了。
【例题 2】[TJOI2018] 游园会
令 \(f(i)\) 为满足下面几条限制的字符串 \(S\) 的个数：
- 长度为 \(n\)，字符集为 \(\{\texttt N,\texttt O,\texttt I\}\)。
- 不包含子串 \(\texttt{NOI}\)。
- 与长度为 \(k\) 的模式串 \(T\) 的最长公共子序列长度为 \(i\)。
对于 \(i\in[0,k]\)，求出 \(f_i\) 的值，对 \(10^9+7\) 取模。
\(1\le n\le 10^3\)，\(1\le k\le 15\)。
我们考虑下面的状态设计：
设 \(dp_{i,j}\) 表示当前匹配至 \(S\) 的第 \(i\) 个字符、\(T\) 的第 \(j\) 个字符时得到的 LCS 长度。
发现难以转移。因为我们不知道这之前的情况。
考虑到一个性质：若我们知道当前 \(T\) 与前 \(i\) 位 \(S\) 匹配后的 LCS 长度 \(f_i\) 这个数组即可转移。
注意到 \(f_i-f_{i-1}\in\{0,1\}\)。
于是状压 \(f\) 的差分数组，使用滚动数组滚掉第一维。再次考虑第 2 个限制。另开一维记录一下匹配到 \(\texttt{NOI}\) 的哪里即可。
代码：
// N: 0, O: 1, I: 2
int f[2][N], trs[N][3];
void init() {
for (int pre = 0 ; pre < (1 << k) ; pre++) {
for (int i = 0 ; i < k ; i++)
f[0][i + 1] = f[0][i] + ((pre >> i) & 1);
for (int j = 0 ; j <= 2 ; j++) {
for (int i = 1 ; i <= k ; i++) {
f[1][i] = max(f[0][i], f[1][i - 1]);
if (a[i] == j) f[1][i] = max(f[1][i], f[0][i - 1] + 1);
}
int nxt = 0;
for (int i = 1 ; i <= n ; i++)
if (f[1][i] > f[1][i - 1]) nxt ^= (1 << (i - 1));
trs[pre][j] = nxt;
}
}
}
ll dp[2][K][3], ans[N];
inline void upd(ll &x, ll y) { x += y, x %= mod; }
int main() {
n = rd(), k = rd();
scanf("%s", s + 1);
for (int i = 1 ; i <= k ; i++)
a[i] = (s[i] == 'N' ? 0 : (s[i] == 'O' ? 1 : 2));
init();
dp[0][0][0] = 1; int nw = 0;
for (int i = 1 ; i <= n ; i++, nw ^= 1) {
memset(dp[nw ^ 1], 0, sizeof(dp[nw ^ 1]));
for (int pre = 0 ; pre < (1 << k) ; pre++) {
for (int i = 0 ; i <= 2 ; i++)
for (int j = 0 ; j <= 2 ; j++) {
if (i == 2 && j == 2)
continue;
int t = 0;
if (j == 0) t = 1;
if (i == 1 && j == 1) t = 2;
upd(dp[nw ^ 1][trs[pre][j]][t], dp[nw][pre][i]);
}
}
}
for (int pre = 0 ; pre < (1 << k) ; pre++)
for (int i = 0 ; i <= 2 ; i++) {
int t = pre, cnt = 0;
while (t) cnt += t & 1, t >>= 1;
upd(ans[cnt], dp[nw][pre][i]);
}
for (int i = 0 ; i <= k ; i++) printf("%lld\n", ans[i]);
return 0;
}
【例题 3】[SNOI2019] 纸牌 (55 分)
有一副纸牌。牌一共有 \(n\) 种，分别标有 \(1,2,...,n\) ，每种有 \(C\) 张。故这副牌总共有 \(nC\) 张。
三张连号的牌 \((i,i+1,i+2)\) 或三张相同的牌 \((i,i,i)\) 可以组成一叠。如果一组牌可以分成若干（包括零）叠，就称其为一组王牌。
你从牌堆中摸了一些初始牌。现在你想挑出一些牌组成一组王牌，求出可能组成的王牌种数，对 \(998244353\) 取模。两组牌相同当且仅当它们含有的每一种牌数量都相同。
对于所有数据，\(1\le n\le 10^{18}\)，\(0\le a_i\le C\le 10^3\)，\(0\le X\le 10^3\)。
只写 55 分做法是因为看不懂题解，再加上本来就不想掌握了。。。
考虑到当给定牌集确定时，判断其是否可以被分为若干叠牌时，贪心匹配显然是正确的，但是这不具有扩展性。
延续贪心的思想，逐种牌加入，考虑如何用一个简小的状态来刻画当前情况来合并等价类，容易发现，我们只关心当前情况下插入后的 \((i-1,i,i+1),(i,i+1,i+2)\) 的对数。
于是，设 \(f_{i,j,k}\) 表示考虑到的牌大小为 \(i\)，\((i-1,i,i+1)\) 的对数为 \(j\)，\((i,i+1,i+2)\) 的对数为 \(k\)。考虑如何进行 \(f_{i,j,k}\to f_{i+1,k,l}\)。
令 \((i,i+1,i+2)\) 为顺子。则出现在顺子中的第 \(i+1\) 种牌共有 \(s=j+k+l\) 张。
于是转移方程为：
\[f_{i+1,k,l}=\begin{cases}f_{i,j,k}\cdot\left(\left\lfloor\dfrac{C-s}{3}\right\rfloor+1\right)&s\ge a_{i+1},\\ f_{i,j,k}\cdot\left(\left\lfloor\dfrac{C-s-3\cdot\left\lceil\frac{a_{i+1}-s}{3}\right\rceil}{3}\right\rfloor+1\right)&s< a_{i+1}.\end{cases} \]由于胡牌的性质，把 \(j,k,l\) 限制到 \([0,3)\)。
转移就行了。可以拿到 55 分，不过应该够了。
据说可以把状态描述成 \(dp_{i,3j+k}\) 然后进行矩阵快速幂。以后再研究。
另外，https://codeforces.com/contest/1110/problem/D 与之状态设计方面存在异曲同工之妙。
【例题 4】[SDOI/SXOI2022] 小 N 的独立集
给定 \(n\) 个点的树的形态以及点的权值范围 \([1,k]\)，对于任意 \(i\in[1,kn]\)，求有多少种权值分配方案，使得树的最大权独立集大小为 \(i\)。
\(1\le n \le 10^3\)，\(1\le k\le 5\)。
4.1 前置知识
4.1.1 最大独立集问题
对于一棵有 \(n\) 个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻。
设一下 \(f_{u,0/1}\) 表示不选/选第 \(u\) 个结点时在 \(u\) 的子树内取得的最大点数，直接转移即可。
4.1.2 最大权独立集问题
一样的，改一下状态含义即可。
4.2 \(n\le 8\)
朴素 dp。直接枚举所有方案填满然后跑一下 4.1.2 即可。
4.3 \(n\le 100\)
启示：经典 dp 模型，这引导我们仿照【例题 1～2】进行 dp of dp。
设 \(g_{u,v_0,v_1}\) 表示当在 4.1.2 模型中 \(f_{u,0}=v_0,f_{u,1}=v_1\) 时的方案数。
转移时模拟 4.1.2 时的转移，考虑将 \(u\) 的儿子 \(v\) 转移到 \(u\) 上：
\[\textbf{\textit{g}}_{u,i+\max(p,q),j+q}=\textbf{\textit g}_{u,i+\max(p,q),j+q}+g_{u,i,j}\times g_{v,p,q} \]上面枚举一下 \(i,j,p,q\) 即可。这里面的 \(\textbf{\textit{g}}\) 表示转移时先不影响 \(g\) 的取值。
这是树上背包，时间复杂度 \(O(n^4k^4)\)。
4.4 \(n\le 10^3\)
上述算法的瓶颈在于方案数已经达到 \(n^3k^2\)。
改设 \(h_{u,0/1}\) 表示 \(u\) 子树内是否强制不选节点 \(u\) 时的最大方案大小，注意到 \(0\le h_{u,0}-h_{u,1}\le val_u\le k\)。于是进行差分。
设 \(g_{u,v_1,d}\) 表示 \(f_{u,0}=v_0+d,f_{u,1}=v_0\) 时的方案数，仍然枚举 \(i,j,p,q\)，则有
\[\textbf{\textit{g}}_{u,i+p+q,\max(j,q)-q}=\textbf{\textit g}_{u,i+p+q,\max(j,q)-q}+g_{u,i,j}\times g_{v,p,q} \]时间复杂度 \(O(n^2k^4)\)，可以通过。
【例题 5】[ZJOI2019] 麻将
可怜找了一套特殊的麻将，它有 \(n\ (5\le n\le 100)\) 种不同的牌，大小分别为 \(1\) 到 \(n\)，每种牌都有 \(4\) 张。
定义面子为三张大小相同或者大小相邻的麻将牌，即大小形如 \(i,i,i\ (1 \le i \le n)\) 或者\(i,i+1,i+2\ (1\le i\le n-2)\)。定义对子为两张大小相同的麻将牌，即大小形如 \(i,i\ (1 \le i \le n)\)。
定义一个麻将牌集合 \(S\) 是胡的当且仅当它的大小为 \(14\) 且满足下面两个条件中的至少一个：
- \(S\) 可以被划分成五个集合 \(S_1\) 至 \(S_5\) 。其中 \(S_1\) 为对子，\(S_2\) 至 \(S_5\) 为面子。
- \(S\) 可以被划分成七个集合 \(S_1\) 至 \(S_7\) ，它们都是对子，且对应的大小两两不同。
可怜先摸出了 \(13\) 张牌，并把剩下的 \(4n-13\) 张牌随机打乱。对于一个排列 \(P\)，可怜定义 \(S_i\) 为可怜事先摸出的 \(13\) 张牌加上 \(P\) 中的前 \(i\) 张牌构成的集合，定义 \(P\) 的权值为最小的 \(i\) 满足 \(S_i\) 存在一个子集是胡的。如果你对麻将比较熟悉，不难发现 \(P\) 的权值就是理论上的最早胡牌巡目数。注意到 \(n\ge 5\) 的时候，\(S_{4n-13}\)总是存在胡的子集的，因此 \(P\) 的权值是良定义的。
现在可怜想要训练自己的牌效，因此她希望你能先计算出 \(P\) 的权值的期望是多少。
【例题 6】[NOI2022] 移除石子
有 \(n\) 堆石子排成一行，第 \(i\) 堆有 \(a_i\) 枚，你的任务是通过如下的操作将所有石子移除：
- 操作一：选择一堆石子，将其中的至少 \(2\) 枚石子移除；
- 操作二：选择一个连续的编号区间 \([l, r]\)（\(1 \le l \le r \le n\)）并满足 \(r - l \ge 2\)，将其中的每一堆石子都恰好移除 \(1\) 枚。
你可以采用任意顺序执行任意多次上述两种操作，直到无法再执行操作为止。若最后你能将所有石子全部移除则胜利。
你或许已经开始计算起了诸如“有多少种本质不同的操作方式”的问题，但实际玩起来你却发现自己总是在输。因此，你打算玩个小花招：在游戏开始时，你在手里偷偷藏有 \(k\) 枚石子，在执行所有操作之前你可以且必须将这些石子放入某一堆或某几堆石子中。你期望这会提高自己的胜率，但也清楚这可能会使自己输掉原本可能胜利的游戏。
现在，你可以自由选择一个初始局面进行游戏，具体而言，每个 \(a_i\) 可以选择 \([l_i, r_i]\) 范围内的任意整数。你希望计算出，在多少种初始局面下，自己存在至少一种获胜的方案。由于答案很大，你只需要输出其对 \(({10}^9 + 7)\) 取模的结果。两个初始局面不同，当且仅当存在至少一个 \(\boldsymbol{1 \le i \le n}\) 使得两者的 \(\boldsymbol{a_i}\) 不相等，注意这里的“初始局面”指的是你放入 \(\boldsymbol{k}\) 枚石子之前的局面。
对于所有数据，有 \(T \le 10\)，\(3 \le n \le 1000\)，\(0 \le l_i \le r_i \le {10}^9\)，\(0 \le k \le 100\)。
对于合法序列计数题，首先必须会判定合法序列，于是考虑 \(l_i=r_i\) 的情况。
先考虑 \(k=0\) 时的情况。我们注意到：
- 所有序列可以转化为长度为 \(3,4,5\) 的序列；
- 我们不会进行两次以上同样的操作二。
例题 5～6 太抽象了，决定先摆烂。
标签：10,le,4.1,石子,笔记,学习,DP,例题,dp From： https://www.cnblogs.com/plenilunesept/p/17590194.html