普通的 LCS 是经典的 DP 问题, 那么如果加上方案数, 则与最短路计数类似的
1. 如果相同, 就加上方案数
2. 如果可以被更新, 就重新统计方案数
但在这一题中, 有一种特殊情况要考虑
如果一个子串,(i-1,j)和 (i,j-1) 都是由 (i-1,j-1) 转移过来, 那么如果在更新 f(i,j)时, 就不可以用 (i-1,j-1) 继续累加, 就应判定这是重复的, 由容斥原理可得, 应当减去这一方案数.
例外, 此题内存限制严格, 需用滚动数组
详细见代码
- #include<bits/stdc++.h>
- const int mod=1e8;
- const int Maxn=5005;
- int f[2][Maxn],sum[2][Maxn];
- char s1[Maxn],s2[Maxn];
- using namespace std;
- inline int read(){
- char c=getchar();int fh=0;
- while(!isdigit(c))c=getchar();
- while(isdigit(c))fh=(fh<<1)+(fh<<3)+(c^48),c=getchar();
- return fh;
- }
- int main(){
- cin>>s1+1>>s2+1;
- int l1=strlen(s1+1)-1,l2=strlen(s2+1)-1;
- sum[0][0]=1;
- for(int i=1;i<=l2;++i)sum[0][i]=1;// 初始化方案数
- for(int i=1;i<=l1;++i){
- sum[i&1][0]=1;
- for(int j=1;j<=l2;++j){
- f[i&1][j]=f[(i-1)&1][j];sum[i&1][j]=sum[(i-1)&1][j];// 考虑 (i-1,j) 的情况
- if(f[i&1][(j-1)]>f[i&1][j])f[i&1][j]=f[i&1][(j-1)],sum[i&1][j]=sum[i&1][j-1];//i,j-1 的情况>就更新
- else if(f[i&1][j-1]==f[i&1][j])sum[i&1][j]=(sum[i&1][j]+sum[i&1][j-1])%mod;//= 就累加
- if(s1[i]==s2[j]){
- if(f[i&1][j]<f[(i-1)&1][j-1]+1)f[i&1][j]=f[(i-1)&1][j-1]+1,sum[i&1][j]=sum[(i-1)&1][j-1];
- else if(f[i&1][j]==f[(i-1)&1][j-1]+1)sum[i&1][j]=(sum[i&1][j]+sum[(i-1)&1][j-1])%mod;// 同理
- }
- else{
- if(f[i&1][j]<f[(i-1)&1][j-1])f[i&1][j]=f[(i-1)&1][j-1],sum[i&1][j]=sum[(i-1)&1][j-1];
- else if(f[i&1][j]==f[(i-1)&1][j-1])sum[i&1][j]=(sum[i&1][j]-sum[(i-1)&1][j-1]+mod)%mod;// 特殊情况, 需要去重
- }
- }
- }
- cout<<f[l1&1][l2]<<endl<<sum[l1&1][l2]<<endl;
- }
来源: http://www.bubuko.com/infodetail-3231612.html