【NOIP2015】子串

一道不怎么简单的dp题

我们定义状态f[i][j][k][val](其中val∈{0,1})表示A串的前i个字符,分成k段,与B串的前j个字符匹配,并且A[i]选/不选的方案数。

那么我们考虑状态的转移,

当a[i]==b[j]时,f[i][j][k][1]可以从f[i-1][j-1][k-1][0],f[i-1][j-1][k][1],f[i-1][j-1][k-1][1]三个状态转移而来;f[i][j][k][0]可以从f[i-1][j][k][1],f[i-1][j][k][0]两个状态转移而来。

当a[i]!=b[j]时,f[i][j][k][1]=0,f[i][j][k][0]可以从f[i-1][j][k][1],f[i-1][j][k][0]转移而来

由于阶段i由且仅由i-1阶段转移而来,所以我们采用滚动数组优化空间,仅存i和i-1两个阶段即可。

上一篇:【数据结构】运输计划 NOIP2015提高组D2T3


下一篇:第十一章、Spring配置文件参数化