> AC ..IN C++..
> 
> haha...
贴一个庆祝一下 6000+ms


#include<iostream>
#include<cmath>
#include<cstdlib>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#pragma GCC optimize (2)
using namespace std;
const double eps=1e-9;
const int mod=7;
const int inf=1e9+9,add=15000;
int dp[mod][30001],ans,pre[30001];
int mat[4][4]={{0,5,5,5},{5,0,4,5},{5,4,0,5},{5,5,5,0}};
char ch[]={'A','G','C','T'};
int pos[128],len[2];
char str[2][55555];
int main()
{
    int i,j,s,p,q,cost,low,high;
    for(i=0;i<4;i++)
       pos[ch[i]]=i;
    while(scanf("%s%s",str[0],str[1])==2)
    {
       len[0]=strlen(str[0]);
        len[1]=strlen(str[1]);
        if(len[0]<len[1])
        {
            swap(len[0],len[1]);
            for(j=0;j<max(len[0],len[1]);j++)
               swap(str[0][j],str[1][j]);
        }
        int vl=(int)(0.45*(len[0]+len[1])+1-eps);
        ans=3*(len[0]-vl+len[1]-vl);
        int dm=len[0]-len[1]; 
        int flag=3*dm%mod;
        memset(dp,-1,sizeof(dp));
        dp[flag][add]=0;
        memset(pre,-1,sizeof(pre));
        for(cost=3*dm;cost<=ans;cost++)
        {
            int low,high,nflag;
            if(cost+mod-1<=ans)
            {
                nflag=(flag+mod-1)%mod;
                low=(3*dm-(cost+mod-1))/6;
                high=(3*dm+cost+mod-1)/6; 
                for(j=low;j<=high;j++)
                   dp[nflag][j+add]=-1;
            }
            low=(3*dm-cost)/6;
            high=(3*dm+cost)/6;
            for(j=high;j>dm;j--)
            {
                int nflag,nj=dp[flag][j+add]-j,ni=dp[flag][j+add];
                if(pre[j+add]>=ni)
                    continue; 
				while(ni<len[0]&&nj<len[1]&&str[0][ni]==str[1][nj])
                {
                    ni++;
                    nj++;
                }
                pre[j+add]=ni;
                if(ni>=len[0]&&nj>=len[1])
                {
                    ans=cost;
                    goto orz;
                }
                if(ni+1<=len[0]&&nj+1<=len[1])
                {
                    nflag=flag+mat[pos[str[0][ni]]][pos[str[1][nj]]];
                    if(nflag>=mod)
                       nflag-=mod;
					if(dp[nflag][j+add]<ni+1)
                        dp[nflag][j+add]=ni+1;
                }
                if(ni+1<=len[0])
                {
                      if(pre[ni+1-nj+add]<ni+1)
                      {
                      	   nflag=(flag+6);
                      	   if(nflag>=mod)
                      	      nflag-=mod;
                             if(dp[nflag][ni+1-nj+add]<ni+1)
                                dp[nflag][ni+1-nj+add]=ni+1;
                        }
                }
                if(nj+1<=len[1])
                {
                      if(pre[ni-nj-1+add]<ni)
                      {
                              if(dp[flag][ni-nj-1+add]<ni)
                                  dp[flag][ni-nj-1+add]=ni;
                      }
                }
            }
            for(j=low;j<=dm;j++)
            {
            	 if(dp[flag][j+add]<0)
                   continue;
                int nflag,nj=dp[flag][j+add]-j,ni=dp[flag][j+add];
                if(pre[j+add]>=ni)
                    continue;
				while(ni<len[0]&&nj<len[1]&&str[0][ni]==str[1][nj])
                {
                    ni++;
                    nj++;
                }
                pre[j+add]=ni;
                if(ni>=len[0]&&nj>=len[1])
                {
                    ans=cost;
                    goto orz;
                }
                if(ni+1<=len[0]&&nj+1<=len[1])
                {
                    nflag=flag+mat[pos[str[0][ni]]][pos[str[1][nj]]];
                    if(nflag>=mod)
                        nflag-=mod;
                    if(dp[nflag][j+add]<ni+1)
                        dp[nflag][j+add]=ni+1;
                }
                if(ni+1<=len[0])
                {
                      if(pre[ni+1-nj+add]<ni+1)
                      {
                      	    nflag=flag;
                      	    if(j==dm)
                      	    {
                      	       nflag=(flag+6);
                      	       if(nflag>=mod)
                      	          nflag-=mod;
						    }
                             if(dp[nflag][ni+1-nj+add]<ni+1)
                                dp[nflag][ni+1-nj+add]=ni+1;
                        }
                }
                if(nj+1<=len[1])
                {
                      if(pre[ni-nj-1+add]<ni)
                      {
                      	     nflag=(flag+6);
                      	     if(nflag>=mod)
                      	        nflag-=mod;
                              if(dp[nflag][ni-nj-1+add]<ni)
                                  dp[nflag][ni-nj-1+add]=ni;
                      }
                }
            }
            flag=(flag+1)%mod;
        }
        orz: 
        printf("%d\n",ans);
    }
    return 0;
}