题解
O(n^3)
#include<stdio.h>
#include<string.h>
int f[1010][1010];
char s1[1010],s2[1010],s[1010];
int max(int x1,int x2)
{
return x1>x2?x1:x2;
}
int main()
{
while(1) {
int n1,n2;
gets(s); n1=strlen(s);
for(int i=1;i<=n1;i++) s1[i]=s[n1-i];
gets(s); n2=strlen(s);
for(int i=1;i<=n2;i++) s2[i]=s[n2-i];
for(int i=0;i<=n1;i++)
for (int j=0;j<=n2;j++) f[i][j]=-10000000;
f[0][0]=0;
for(int i=1;i<=n1;i++) f[i][0]=-1;
for(int i=1;i<=n2;i++) f[0][i]=-1;
int maxn=-1,maxx=-100;
for(int i=1;i<=n1;i++)
for(int j=1;j<=n2;j++)
{
f[i][j]=f[i-1][j]-1;
maxn=-100;
if(s1[i]==s2[j]) maxn=max(maxn,f[i-1][j-1]+2);
else maxn=max(maxn,f[i-1][j-1]);
for(int k=j-1;k>=1;k--) maxn=max(maxn,f[i][k]-1);
for(int k=i-1;k>=1;k--) maxn=max(maxn,f[k][j]-1);
f[i][j]=max(maxn,f[i][j]);
maxx=max(maxx,f[i][j]);
}
printf("%d\n",maxx);
}
return 0;
}
O(n^2)
#include<iostream>
using namespace std;
int n,m;
char s1[1010],s2[1010];
short f[1010][1010];
int p[1010][1010];
const int d[3][2]={-1,0,0,-1,-1,-1};
int main()
{
freopen("align.in","r",stdin);
freopen("align.out","w",stdout);
gets(s1); gets(s2);
strrev(s1); strrev(s2);
n=strlen(s1); m=strlen(s2);
memset(f,128,sizeof(f));
memset(p,-1,sizeof(p));
f[0][0]=0;
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j)
for(int k=0;k<3;++k){
int x=i+d[k][0],y=j+d[k][1],z;
if(x>=0&&y>=0){
if(i!=0&&j!=0)
if(k==2){
short tmp=f[x][y]+(s1[i-1]==s2[j-1]?2:0);
if(tmp>f[i][j]){
f[i][j]=tmp;
p[i][j]=k;
continue;
}
}
if(p[x][y]!=0&&p[x][y]!=1&&!(x==n||y==m))
z=-1;
else z=0;
if(f[x][y]+z>f[i][j]){
f[i][j]=f[x][y]+z;
p[i][j]=k;
}
}
}
printf("%d\n",f[n][m]);
return 0;
}
posted on 2009-04-13 11:00
xfstart07 阅读(103)
评论(0) 编辑 收藏 引用 所属分类:
代码库