背景
and I know that my heart will go on.
We'll stay forever this way.
You are safe in my heart.
And my heart will go on and on.
描述
输入格式
输出格式
样例输入
INeedYou IMissYou ILoveYou
样例输出
4 15
数据范围与约定
样例解释
来源
这题是统计公共子序列个数+去重
正解用了容斥原理,并且允许空串。
F[I][J][K]=2F[I-1][J-1][K-1]-F[I'-1][J'-1][K'-1] I',J',K'为I,J,K,之前出现a[i],b[j],c[k]的位置(没有就不用减)
假设之前已经去重,那么F[I][J][K]只需与F[I'-1][J'-1][K'-1]去重。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<functional> #include<algorithm> #include<cctype> using namespace std; #define F (2769433) #define MAXN (100+10) #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<=n;i++) int len1,len2,len3,f[MAXN][MAXN][MAXN],pre1[MAXN],pre2[MAXN],pre3[MAXN],s[500]; char a[MAXN],b[MAXN],c[MAXN]; void make_pre(char *a,int n,int *pre) { memset(s,128,sizeof(s)); memset(pre,0,sizeof(pre)); For(i,n) { a[i]=tolower(a[i]); pre[i]=s[a[i]]; s[a[i]]=i; } } int main() { memset(f,0,sizeof(f)); scanf("%s%s%s",a+1,b+1,c+1);a[0]=b[0]=c[0]=' '; len1=strlen(a)-1,len2=strlen(b)-1,len3=strlen(c)-1; make_pre(a,len1,pre1); make_pre(b,len2,pre2); make_pre(c,len3,pre3); int cnt=0; For(i,len1) For(j,len2) For(k,len3) if (a[i]==b[j]&&b[j]==c[k]) f[i][j][k]=f[i-1][j-1][k-1]+1; else f[i][j][k]=max(max(f[i-1][j][k],f[i][j-1][k]),f[i][j][k-1]); cnt=f[len1][len2][len3]; // memset(f,0,sizeof(f)); Rep(i,len1) Rep(j,len2) Rep(k,len3) f[i][j][k]=1; For(i,len1) For(j,len2) For(k,len3) { f[i][j][k]=0; if (a[i]==b[j]&&b[j]==c[k]) { f[i][j][k]=(10*F+f[i-1][j-1][k-1]*2)%F; if (pre1[i]>0&&pre2[j]>0&&pre3[k]>0) f[i][j][k]=(F+f[i][j][k]-f[pre1[i]-1][pre2[j]-1][pre3[k]-1])%F; // if (!pre1[i]||!pre2[j]||!pre3[k]) f[i][j][k]--; } else { f[i][j][k]=(10*F+f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i-1][j-1][k]-f[i][j-1][k-1]-f[i-1][j][k-1]+f[i-1][j-1][k-1])%F; } } printf("%dn%dn",cnt,(F+f[len1][len2][len3]-1)%F); return 0; }