POJ 1080 Human Gene Functions

DP強化週間。
A,C,G,Tからなる文字列が2つ与えられて、文字列に'-'をいくつか挿入して2つの文字列を同じ長さにする。ただし2つの文字列の同じ位置に'-'は来ないようにする。文字間の対応にはスコアが与えられる。このスコアを最大化するような対応を見つけ、そのスコアを返す問題。

dp[i][j]:=(文字列1のi文字目までと文字列2のj文字目までを対応付ける時の最大スコア)でDP。
文字列1をs、文字列2をtとすると、

- s[i] == t[j] となる時
dp[i + 1][j + 1] = dp[i][j] + score(s[i]とt[j])

- そうでない時
dp[i + 1][j + 1] = max(dp[i + 1][j] + score('-'とt[j]),//sの'-'とtのj文字目
	               dp[i][j + 1] + score(s[i]と'-'),//sのi文字目とtの'-'
		       dp[i][j]     + score(s[i]とt[j]));//sのi文字目とtのj文字目

となる。計算量は文字列の長さをL,Mとして使用するアルファベットの種類をNとすると
O(LM*log(N+1))位になるのかな。

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[101][101];

int main(){
  int n;
  cin >> n;
  map<char, int> dic;
  dic['A'] = 0;  dic['C'] = 1;  dic['G'] = 2;  
  dic['T'] = 3;  dic['-'] = 4;

  while(n--){
    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 i = 0; i < M; i++)
      dp[0][i + 1] = dp[0][i] + mat[ dic['-'] ][ dic[t[i]] ];

    for(int i = 0; i < L; i++){
      for(int j = 0; j < M; j++){
	if(s[i] == t[j]){
	  dp[i + 1][j + 1] = dp[i][j] + mat[ dic[s[i]] ][ dic[t[j]] ];
	}else{
	  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;
}

最初に初期化するの忘れてて答えが合わなかった。
http://d.hatena.ne.jp/keitanxkeitan/20100302/1267508194
の方のソース見て気づいた。
少しずつわかるようになってきているので引き続き頑張りたい。(｀・ω・´)