#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
char s1[50010],s2[50010];
int n1,n2;
int t[50003],b[50003];
int d[4][4]={{0,5,5,5},{5,0,4,5},{5,4,0,5},{5,5,5,0}};
int main()
{
	int i,j,check;
	while(scanf("%s",s1)!=EOF)
	{
		if(scanf("%s",s2)==EOF)
			break;
		n1=(int)strlen(s1);
		n2=(int)strlen(s2);
		for(i=0;i<n1;i++)
		{
			switch(s1[i])
			{
			case 'A':
				s1[i]=0;
				break;
			case 'G':
				s1[i]=1;
				break;
			case 'C':
				s1[i]=2;
				break;
			case 'T':
				s1[i]=3;
				break;
			}
		}
		for(i=0;i<n2;i++)
		{
			switch(s2[i])
			{
			case 'A':
				s2[i]=0;
				break;
			case 'G':
				s2[i]=1;
				break;
			case 'C':
				s2[i]=2;
				break;
			case 'T':
				s2[i]=3;
				break;
			}
		}
		check=10;
		i=0;
		j=i-n1/check;
		if(j<0)
			j=0;
		for(;j<=i+n1/check && j<=n2;j++)
		{
			b[j]=100000000;
		}
		b[0]=0;
		for(i=0;i<=n1;i++)
		{
			j=i-n1/check;
			if(j<0)
				j=0;
			for(;j<=i+n1/check && j<=n2;j++)
			{
				t[j]=b[j];
			}
			j=i+1-n1/check;
			if(j<0)
				j=0;
			for(;j<=i+1+n1/check && j<=n2;j++)
			{
				b[j]=100000000;
			}
			j=i-n1/check;
			if(j<0)
				j=0;
			for(;j<=i+n1/check && j<=n2;j++)
			{
				if(i<n1 && j<n2 && b[j+1]>d[s1[i]][s2[j]]+t[j])
					b[j+1]=d[s1[i]][s2[j]]+t[j];
				if(b[j]>3+t[j])
					b[j]=3+t[j];
				if(t[j+1]>3+t[j])
					t[j+1]=3+t[j];
			}
		}
		printf("%d\n",t[n2]);
	}
	return 0;
}

this is my code.

please help me

• 不要随便挑战AC只有7的题目。 (0) H2_CPP 2006-02-04 14:56:16
  • 我就从来不做AC小于20的题，因为。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。偶是菜鸟 (0) oeym 2006-02-04 16:40:08
• Re:why tle???????????? (9) cuiaoxiang 2006-02-04 17:38:46
• They above r saying : it's very difficult (more than u think) .. :> (1720) JUDAS 2006-02-09 21:36:41