POJ.1080 Human Gene Functions

1.Problem
http://poj.org/problem?id=1080

2.Idea
DP + string

3.Source

 int mat[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, 0,  
 };  
 int dp[102][102];  
 int main()  
 {  
      int t;  
      cin >> t;  
      map<char, int> dic;  
      dic['A'] = 0; dic['C'] = 1; dic['G'] = 2;  
      dic['T'] = 3; dic['-'] = 4;  
      while (t--) {  
           int l, m;  
           string s, t;  
           cin >> l >> s;  
           cin >> m >> t;  
           memset(dp, 0, sizeof dp);  
           for (int i = 0; i < l; i++) dp[i + 1][0] = dp[i][0] + mat[dic[s[i]]][dic['-']];  
           for (int j = 0; j < m; j++) dp[0][j + 1] = dp[0][j] + mat[dic['-']][dic[t[j]]];  
           for (int i = 0; i < l; i++) {  
                for (int j = 0; j < m; j++) {  
                     dp[i + 1][j + 1] = max(dp[i + 1][j] + mat[dic['-']][dic[t[j]]],  
                                           max(dp[i][j + 1] + mat[dic[s[i]]][dic['-']],  
                                       dp[i][j] + mat[dic[s[i]]][dic[t[j]]]));                           
                }  
           }  
           cout << dp[l][m] << endl;  
      }  
      return 0;  
 }