HDU 1080

http://acm.hdu.edu.cn/showproblem.php?pid=1080

二维最长公共子序列

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std ;

char s1[105],s2[105];

int tab[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}};
//dp[i][j]表示长i和j的字符串的最长公共子序列 
int dp[105][105];
int mp[2][105];
int cal(char x){
    if(x=='A')return 0;
    if(x=='C')return 1;
    if(x=='G')return 2;
    if(x=='T')return 3; 
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%s%d%s",&n,s1,&m,s2);
        for(int i=0;i<2;i++){
            if(!i){
                for(int j=0;j<n;j++)
                    mp[0][j]=cal(s1[j]);
            }
            else{
                for(int j=0;j<m;j++)
                    mp[1][j]=cal(s2[j]);
            }
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            dp[i][0]=dp[i-1][0]+tab[mp[0][i-1]][4];
        for(int i=1;i<=m;i++)
            dp[0][i]=dp[0][i-1]+tab[mp[1][i-1]][4];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=max(dp[i-1][j]+tab[mp[0][i-1]][4],max(dp[i][j-1]+tab[mp[1][j-1]][4],dp[i-1][j-1]+tab[mp[0][i-1]][mp[1][j-1]]));
            }
        }
        printf("%d
",dp[n][m]);
    }
    return 0;
}