題目鏈接：http://61.187.179.132/JudgeOnline/problem.php?id=2423

題意：求兩個(gè)串的LCS以及LCS的個(gè)數(shù)。

思路：

int f[2][N],g[2][N]; char s[N],t[N]; int n,m;void add(int &x,int y) {x+=y;x%=mod; }int main() {RD(s); n=strlen(s)-1; RD(t); m=strlen(t)-1; int i,j;int pre=0,cur=1;for(i=0;i<=m;i++) g[0][i]=1;g[pre][0]=1;FOR1(i,n) {clr(f[cur],0);clr(g[cur],0);g[cur][0]=1;FOR1(j,m){if(s[i-1]==t[j-1]){f[cur][j]=f[pre][j-1]+1;g[cur][j]=g[pre][j-1];if(f[cur][j-1]==f[cur][j]) add(g[cur][j],g[cur][j-1]);if(f[pre][j]==f[cur][j]) add(g[cur][j],g[pre][j]);}else{f[cur][j]=max(f[cur][j-1],f[pre][j]);if(f[cur][j-1]==f[cur][j]) add(g[cur][j],g[cur][j-1]);if(f[pre][j]==f[cur][j]) add(g[cur][j],g[pre][j]);if(f[pre][j-1]==f[cur][j]) add(g[cur][j],-g[pre][j-1]);}}swap(pre,cur);}if(g[pre][m]<0) g[pre][m]+=mod;PR(f[pre][m]);PR(g[pre][m]); }

?

總結(jié)

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

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