a little idea

noip 2015 day2 t2

设$$f[i][j][k]$$
为答案
$$f[i][j][k]=f[i-1][j][k]+(a[i]==b[j])*f[i-1][j-1][k-1]+(a[i-1]==b[j-1])*(f[i-1][j-1][k])$$
然后发现有问题
接下来就是神奇的地方了
我们发现这个方法有一个bug 也就是算$$(a[i-1]==b[j-1])*(f[i-1][j-1][k])$$这一块的时候
我们默认了f[i-1][j-1][k]这个状态i-1这个位置是选的。实际上是不一定的
于是我们新建一个状态$$g[i][j][k]$$
表示i这个位置是选的于是$$g[i][j][k]=(a[i]==b[j])*(f[i-1][j-1][k-1],g[i-1][j-1][k])$$ $$f[i][j][k]=f[i-1][j][k]+g[i][j][k]$$
于是就解决了好妙妙

发表评论

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