#include <stdio.h>
#include <string>
#define MAX 5000
using namespace std;

long d[2][MAX];
int map[5][5]={{5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},{-1,-2,-2,5,-1},{-3,-4,-2,-1,-127}};
int t;
int a[MAX],b[MAX];
char s1[MAX],s2[MAX];
int l1,l2;

int dp()
{
    int i,j,k;
    //for(i=1;i<=l1;i++) d[i][0]=map[a[i]][4];      //第二条串不取
    //for(i=1;i<=l2;i++) d[0][i]=map[4][b[i]];
    d[0][0]=0,d[1][0]=map[a[1]][4],d[0][1]=map[4][b[1]];          //d[0][0]应为0，表示都不取 
    t=1;
    for(i=1;i<=l1;i++){
         for(j=1;j<=l2;j++){
              /*    这样就ac了
              d[i][j]=-127;
              d[i][j]=max(d[i][j],d[i-1][j-1]+map[a[i]][b[j]]);
              d[i][j]=max(d[i][j],d[i][j-1]+map[4][b[j]]);
              d[i][j]=max(d[i][j],d[i-1][j]+map[a[i]][4]);
              */
              /*    但如下就wa   */
              d[t][j]=-127;
              d[t][j]=max(d[t][j],d[1-t][j-1]+map[a[i]][b[j]]);
              d[t][j]=max(d[t][j],d[t][j-1]+map[4][b[j]]);
              d[t][j]=max(d[t][j],d[1-t][j]+map[a[i]][4]);
         }
         for(j=1;j<=l2;j++) printf("%d ",d[t][j]);
         printf("\n");
         t=1-t;    
    } 
    return d[1-t][l2];/*不滚动则返回d[l1][l2]*/
}

void trans()
{
     int i;
     for(i=0;i<l1;i++){
         switch(s1[i]){
             case 'A': a[i+1]=0; break;
             case 'C': a[i+1]=1; break;
             case 'G': a[i+1]=2; break;
             case 'T': a[i+1]=3; break;
             case '-': a[i+1]=4; break;
         }
     }
     for(i=0;i<l2;i++){
         switch(s2[i]){
             case 'A': b[i+1]=0; break;
             case 'C': b[i+1]=1; break;
             case 'G': b[i+1]=2; break;
             case 'T': b[i+1]=3; break;
             case '-': b[i+1]=4; break;
         }
     }
     return;
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int c;
    scanf("%d",&c);
    while(c--){
        scanf("%d%s",&l1,&s1);
        scanf("%d%s",&l2,s2);
        trans();
        printf("%ld\n",dp());
    }
    return 0;
}

• Re:为什么滚动数组过不了？只是将对第一维的扫描改为滚动下标，就wa？ (22) ss08zhangchi 2011-02-14 17:13:26