Dp of Dp 可以类比普通的 AC 自动机上跑 dp。
以 LG4590 [TJOI2018]游园会 为例。
内层其实是一个 LCS 的 dp，考虑建出一个 LCS 自动机。
观察 LCS 的方程 \(f_{i,j} = \max f_{i,j-1},f_{i-1,j},f_{i-1,j-1}+(A_i==B_j)\)。
我们可以考虑将所有可能的 \(f_i\) 压成一个个节点。
那么就可以通过枚举新加进来的 \(A\) 构建出我们理想中的 LCS 自动机。
真简单。
标签：LCS,Note,Dp,游园会,自动机,dp From： https://www.cnblogs.com/1l2u3o/p/17005867.html