2023.8.13 DP套DP
[TJOI2018] 游园会
luogu link
首先很容易想到 \(f_{i, 0/1/2}\) 表示考虑兑奖串的前 \(i\) 位 \(\texttt{NOI}\)的出现情况为 \(0/1/2\) 的方案数
考虑转移
首先我们考虑 \(O(n^2)\) 的 \(LCS\) 求法
设 \(g_{x, y}\) 表示考虑 \(S\) 串的前 \(x\) 位 \(T\) 串的前 \(y\) 位的 \(LCS\)
那么显然有 \(g_{x, y} = max(g_{x - 1, y}, g_{x, y - 1}, g{x - 1, y - 1} + (S_x == T_y))\)
那么假如说我把这个 \(g\) 数组放到 \(f\) 数组的第三维 转移的时候考虑枚举 \(y\)
我们发现 对于同一个 \(x\) 而言 它的 \(y\) 每一位最多只差 \(1\)
又因为 \(y\) 显然只有 \(15\) 个 我们考虑将其差分 然后用 \(f_i\) 的第 \(j\) 位表示这个差分数组 那我们就可以状压这个差分数组 然后把它放到 \(f\) 数组的第三维
每次转移的时候 枚举兑奖串的第 \(i + 1\) 位 然后用状压的状态转移即可