DP套DP听名字猜不到它是个什么东西。接下来用一道例题P459TJOI2018游园会来解释DP套DP。游园会参考资料。题目描述小豆参加了NOI的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是\(\texttt{N}\)、\(\texttt{O}\)、\(\texttt{I}\)的字样。在会场上他

将内层DP的结果作为外层DP的状态进行DP。P10614BZOJ3864Heromeetdevil考虑LCS的转移，\(g_{i,j}=g_{i-1,j-1}+1[s_i=t_j]\)或\(g_{i,j}=\max(g_{i-1,j},g_{i,j-1})[s_i\net_j]\)。一个朴素的想法是，设\(f_{i,s}\)表示\(T\)的前\(i\)位，与\(S\)的LCS数组为

所谓dp套dp，实际上就是在说求解一个dp的过程中，我们用另一个dp求解出他应该从某个状态转移到另一个状态。考虑一下这道题，首先求LCS的dp如下：\[dp_{i,j}=\max\{dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+[s_i==t_j]\}\]显然，当\(i\)固定的时候，\(dp_{i,j}\)是单调不降的，且相邻两