題目傳送門：http://www.lydsy.com/JudgeOnline/problem.php?id=2423

　　題目大意：求兩個字符串的最長公共子序列長度和最長公共子序列個數。

　　這道題的話，對于神犇來說，肯定是一眼看出狀態轉移方程的。而我這個蒟蒻，看了幾篇博客之后才看懂。。。

　　第一問模板lcs，大家肯定都會，就是設f[i][j]為A串跑到第i位，B串跑到第j為時的最長公共子序列長度，然后就有：

　　　　f[i][j]=f[i-1][j-1]+1　　(a[i]==b[j])

　　　　　　 ?=max(f[i-1][j],f[i][j-1])　　(a[i]!=b[j])　　（原諒我不會編輯公式）

　　我就解釋一下第二問的方程。先設g[i][j]為A串跑到第i位，B串跑到第j為時的最長公共子序列個數，方程就是這樣：

　　　　g[i][j]=g[i-1][j-1]

　　　　　　　　+g[i-1][j]　　(f[i][j]==f[i-1][j])

　　　　　　　　+g[i][j-1]　　(f[i][j]==f[i][j-1])

　　　　　　　　(a[i]==b[j])

　　　　　　　=g[i-1][j]　　(f[i][j]==f[i-1][j])

　　　　　　　 +g[i][j-1]　　(f[i][j]==f[i][j-1])

　　　　　　　 -g[i-1][j-1]　　(f[i][j]==f[i-1][j-1])

　　　　　　　　(a[i]!=b[j])

　　這里當a[i]和b[j]相同時，g[i-1][j],g[i-1][j-1],g[i][j-1]這三個的最長公共子序列不會重復，因為這里的g[i-1][j-1]實際上還要在末尾添加上a[i]（或b[j]），因此這些lcs全都是以a[i],b[j]結尾的，而g[i-1][j]不包含以a[i]結尾的lcs，g[i][j-1]不包含以b[j]結尾的lcs，因此這三類lcs不會重復，可以直接相加。

　　當a[i]與b[j]不同時，最后當f[i][j]==f[i-1][j-1]時要減去g[i-1][j-1]就是因為這時g[i-1][j-1]被分別包含在g[i-1][j]和g[i][j-1]中，算了兩次，要把重復的減掉。

　　于是就可以愉快地AC這道題了。

　　還有，一定要用滾動數組，不然爆！空！間！

丑代碼：

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int mod=100000000; int f[2][5010],g[2][5010]; char a[5010],b[5010]; int main() {int i,j,n,m;scanf("%s%s",a,b);n=strlen(a)-1; m=strlen(b)-1;for(i=0;i<=m;i++)g[0][i]=1; g[1][0]=1;for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i-1]==b[j-1]){f[i&1][j]=f[i&1^1][j-1]+1;g[i&1][j]=(g[i&1^1][j-1]+(f[i&1^1][j]==f[i&1][j])*g[i&1^1][j]+(f[i&1][j-1]==f[i&1][j])*g[i&1][j-1])%mod;}else{if(f[i&1^1][j]>f[i&1][j-1])f[i&1][j]=f[i&1^1][j];else f[i&1][j]=f[i&1][j-1];g[i&1][j]=((f[i&1^1][j]==f[i&1][j])*g[i&1^1][j]+(f[i&1][j-1]==f[i&1][j])*g[i&1][j-1]-(f[i&1][j]==f[i&1^1][j-1])*g[i&1^1][j-1]+mod)%mod;}printf("%d\n%d",f[n&1][m],g[n&1][m]); } View Code

?

轉載于:https://www.cnblogs.com/quzhizhou/p/6978170.html

總結

以上是生活随笔為你收集整理的【bzoj2423】最长公共子序列[HAOI2010]（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。