給你序列A和B，求出他們LCS的方案數(shù)，|A|,|B|<=5000

dp套dp經(jīng)典題目，我們考慮先求出LCS，令f[i][j]表示處理到序列A的第i位，B序列的第j位時的LCS長度

那么轉(zhuǎn)移很顯然，現(xiàn)在考慮如何統(tǒng)計答案

我們設g[i][j]為當處理到序列A的第i位，B序列的第j位時LCS的方案數(shù)

顯然我們要考慮f[i][j]的轉(zhuǎn)移情況

若f[i][j]=f[i-1][j-1]+1 那么g[i][j]=g[i-1][j-1]

否則我們看f[i][j]是否和f[i-1][j]和f[i][j-1]相等，如果是就分別對應加上g[i-1][j]和g[i][j-1]

注意，若有f[i][j]=f[i-1][j]=f[i][j-1]那么g[i][j]要減去g[i-1][j-1]（可以類比于二維前綴和）

答案就是g[n][m]

#include<stdio.h> #include<string.h> #include<algorithm> #define M 1000000007 using namespace std; inline void ad(int& x,long long y){ x=(x+y+M)%M; } int f[5010][5010],g[5010][5010],n,m; char a[5010],b[5010]; int main(){freopen("lcs.in","r",stdin);freopen("lcs.out","w",stdout);scanf("%s%s",a+1,b+1);n=strlen(a+1); m=strlen(b+1);for(int i=0;i<=n;++i) g[i][0]=1;for(int j=0;j<=m;++j) g[0][j]=1;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;else f[i][j]=max(f[i-1][j],f[i][j-1]);if(f[i][j]==f[i][j-1]) ad(g[i][j],g[i][j-1]);if(f[i][j]==f[i-1][j]) ad(g[i][j],g[i-1][j]);if(a[i]==b[j]) ad(g[i][j],g[i-1][j-1]);if(f[i-1][j-1]==f[i][j-1]&&f[i-1][j-1]==f[i-1][j]&&f[i][j]==f[i-1][j])ad(g[i][j],-g[i-1][j-1]);}}printf("%d\n%d",f[n][m],g[n][m]); }

轉(zhuǎn)載于:https://www.cnblogs.com/Extended-Ash/p/7887162.html

總結(jié)

以上是生活随笔為你收集整理的Jzoj5237 最长公共子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。