NOIP 2015系列解题报告 – [题组/NOIP]

Day2 T2 子串

你可以点击这个链接下载全部的AC代码

题目传送门(LOJ)

题解 :

DP

状态 :

设状态F[i][j][k]表示A串匹配到i,B串匹配到j,已经拿出了k个子串的方案数.

再设G[i][j][k]同样表示上面的方案数, 并有一附加条件:i没有选.

这个状态挺暴力的, 起初suika看了说好像不行, 但是是没什么问题的, 当然, 他有一种更好的做法

状态G设立的目的就是方便使k转移到k+1

转移 :

$f[i+1][j+1][k] += f[i][j][k] \;\;\;\; [a[i+1] b[j+1]]f[i+1][j+1][k+1] += f[i][j][k]\;\;\;\;[a[i+1] b[j+1]]f[i+1][j+1][k+1] += g[i][j][k]\;\;\;\;[a[i+1] b[j+1]]g[i+1][j][k] += f[i][j][k]g[i+1][j][k] += g[i][j][k]$

其中第一维只和i, i+1有关, 可以滚动

复杂度O(NMK)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注