xfstart07
Get busy living or get busy dying

题解

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 阅读(116) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理