内容目录
Problem 1040 基因序列相似性问题
Accept: 59 Submit: 548
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
Genotype 是一个有限的基因序列集。它的每个成员都是由大写的英文字母A-Z组成，不同的字母表示不同种类的基因。一个基因种类可以分化成为若干新的基因种类。这种分化一般呈树状结构。树根处的基因序列称为母序列。基因序列中含有母序列的基因子序列称为本质基因子序列。生物信息学家们在研究Genotype 基因序列时，需要研究同一种类基因序列的相似性。对于同一种类的2个基因序列X和Y，已知它们的母序列P，基因序列X和Y的最长公共本质基因子序列给出其相似性的准确刻画。为了有效地分析基因序列的相似性，科学家们希望设计出一个高效的计算程序，能对给定的基因序列X，Y和它们的母序列P，快速计算出基因序列X和Y的最长公共本质基因子序列的长度。
编程任务:
给定基因序列X，Y和母序列P，计算出基因序列X和Y的最长公共本质基因子序列的长度。
Input
输入数据的前3行中每行有一个正整数，分别表示序列X，Y和P的长度m，n和r（1≤m,n,r≤1000）。接下来的3行给出序列X，Y和P。
Output
在屏幕上输出基因序列X和Y的最长公共本质基因子序列的长度。如果基因序列X和Y没有以P为母序列的公共本质基因子序列，则输出0。
Sample Input
331ABCBCAA
Sample Output
1
这题是为了找省选题无意发现的，原问题的加强版。
解法：
首先我有一个用i滚动的做法，反正是T了，正误不明。。。
#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);
while (scanf("%d%d%d",&n,&m,&p)==3)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
for (int k=0;k<=min(i,j);k++)
{
f[i%2][j][k]=max(f[i%2][j-1][k],f[(i-1)%2][j][k]);
if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(i-1)%2][j-1][k-1]||k==1)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k-1]+1,f[i%2][j][k]);
if ((a[i]==b[j])&&(f[(i-1)%2][j-1][k]||k==0)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k]+1,f[i%2][j][k]);
}
for(int j=1;j<=m;j++)
for (int k=1;k<=p;k++)
f[(i+1)%2][j][k]=0;
}
if (f[n%2][m][p]<p) cout<<"0"<<endl;
else cout<<f[n%2][m][p]<<endl;
}
return 0;
}
找到反例请回复我.
再来说说正解(输出时记得输的是f[p%2][n][m]不是f[k%2][n][m]，变量名乱设害死人）
#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);
while (scanf("%d%d%d",&n,&m,&p)!=EOF)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
int k=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
}
bool flag=1;
int ta=MAXN,tb=MAXN,mina=1,minb=1;
for (int k=1;k<=p&&flag;k++)
{
flag=0;
for (int i=mina-1;i<=n;i++)
for (int j=minb-1;j<=m;j++)
f[k%2][i][j]=0;
for (int i=mina;i<=n;i++)
for (int j=minb;j<=m;j++)
{
f[k%2][i][j]=0;
if ((a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
{
f[k%2][i][j]=f[(k%2)^1][i-1][j-1]+1;
flag=1;ta=min(ta,i);tb=min(tb,j);
}
else if (a[i]==b[j]&&b[j]==c[k]) continue;
else if ((a[i]==b[j])&&(f[k%2][i-1][j-1])) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
else if (a[i]==b[j]) continue;
else f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
}
mina=ta;minb=tb;
ta=tb=MAXN;
}
/*
if (!flag)
{
if (f[k%2][n][m]>=k) while (1);
}
*/
if (!flag) printf("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}
很直观的Dp。。
#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);
while (scanf("%d%d%d",&n,&m,&p)!=EOF)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
int k=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
}
bool flag=1;
int ta=MAXN,tb=MAXN,mina=1,minb=1;
for (int k=1;k<=p&&flag;k++)
{
flag=0;
for (int i=mina-1;i<=n;i++)
for (int j=minb-1;j<=m;j++)
f[k%2][i][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])) 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 (!flag)
{
if (f[k%2][n][m]>=k) while (1);
}
*/
if (!flag) printf("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}
要考虑从f[k-1][i-1][j-1],f[k][i-1][j-1],f[k][i-1][j],f[k][i][j-1]转移的情况,输出记得清0.
事实上，关于数组清0部分，我们还可以做得更好
#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);
while (scanf("%d%d%d",&n,&m,&p)!=EOF)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
int k=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
}
bool flag=1;
int ta=MAXN,tb=MAXN,mina=1,minb=1;
for (int k=1;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; //只要把边界情况赋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])) 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 (!flag) printf("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}
不妨把对k=0的特判写在一起
#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("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}