P4590 [TJOI2018] 游园会
题意
小豆参加了NOI的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是\(N, O, I\)的字样。在会场。上他收集到了\(K\)个奖章组成的串。兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。现在已知兑奖串长度为\(N\)，并且在兑奖串上不会出现连续三个奖章为\(NOI\)，即奖章中不会出现子串\(NOI\)。现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。
题解
设我们求的串为 \(A\) 串，给的串为 \(B\) 串。
我们先考虑怎么求 \(lcs\) ，有一个暴力 \(dp\) ， \(f_{i,j}\) 表示 \(A\) 串的决策点在 \(i\) ，\(B\) 串的决策点在 \(j\) 的 \(lca\) 长度。
\[f_{i,j} = max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[a_i=b_j]) \]正确性显然。
但是我们要求的是 \(lcs\) 长度为 \(k\) 的合法 \(A\) 串数量。
这个东西的合法性都需要用 \(dp\) 来确定，发现我们不能用简单的 \(dp\) 来计数。
有一个很nb的东西叫做 \(dp\) 套 \(dp\)，顾名思义我们把一个 \(dp\) 压入另一个 \(dp\) 的状态来操作。
一个比较暴力的办法是设 \(g_{i,S}\)，决策点在 \(i\)，\(f\) 数组状态为 \(S\) 的方案数，\(S\) 是一个二维数组，然后我们对 \(S\) 进行 \(dp\) 得到下一个状态进行转移。
这时候的状态数很爆炸，发现我们并不需要将整个 \(f\) 的存下来，对于决策点 \(i\) ，我们 \(dp\) 得到下一个状态的地方只有 \(f_i\)，所以我们可以将状态简化。
\(g_{i,S}\) 表示决策点在 \(i\)，\(f_i\) 的状态为 \(S\) 的方案数，\(S\) 是一个一维数组，这样我们可以只通过上一层即 \(f_{i-1}\) 这一层来得到下一个状态。
这时候已经可以做了，但是还可以再简化状态然后有更方便的写法。
注意到 \(f_{i,j}\) 与 \(f_{i,j-1}\) 的差值只能为 \(0,1\)，所以我们就不用存具体的数值，只需要存差分序列即可，由于只有 \(0,1\)，所以使用状压储存。
然后我们就完成了 \(lcs\) 长度为 \(i\) 的个数统计。
然后考虑如何解决不存在 NOI，的条件，这个比较简单，可以通过简单的添加状态解决。
\(g_{i,S,k}\) 表示决策点在 \(i\)，\(f_i\) 的状态为 \(S\)，NOI填了 \(k(k \leq 2)\) 位的方案数。
时间复杂度 \(O(nk2^k)\)，code
...
这是我第一次写 \(dp\) 套 \(dp\)，可能会有些问题。
我们的外层 \(dp\) 进行正常的 \(dp\)，内层 \(dp\) 得到下一个状态。