FZU 1040(基因序列相似性问题-CLCS)
Problem Description Input Output Sample Input Sample Output#include<cstdio>#include<cstring>#include<algorithm>#include<functional>#include<iostream>#include<cstdlib>using namespace std;#define MAXN (1000+10)int f[2][MAXN][MAXN];char a[MAXN],b[MAXN],c[MAXN];int n,m,p;int main(){//freopen("fzu1040.out","r",stdin);c[0]=' ';while (scanf("%d%d%d",&n,&m,&p)!=EOF){scanf("%s%s%s",a+1,b+1,c+1);bool flag=1;int ta=MAXN,tb=MAXN,mina=1,minb=1;for (int k=0;k<=p&&flag;k++){flag=0;for (int i=mina-1;i<=n;i++)f[k%2][i][minb-1]=0;for (int j=minb-1;j<=m;j++)f[k%2][mina-1][j]=0;for (int i=mina;i<=n;i++)for (int j=minb;j<=m;j++){f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1)) {f[k%2][i][j]=max(f[(k%2)^1][i-1][j-1]+1,f[k%2][i][j]);flag=1;ta=min(ta,i);tb=min(tb,j);}if ((a[i]==b[j])&&(f[k%2][i-1][j-1]||k==0)) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);}mina=ta;minb=tb;ta=tb=MAXN;if (!k) {flag=1;mina=minb=1;}}if (!flag) printf("0\n");else printf("%d\n",f[p%2][n][m]);}return 0;}