POJ 2192 Zipper

DP強化週間。
文字列A,B,Cが与えられて、A,Bをそれぞれの文字順序を守って組み合わせた時、Cが得られるか判定する。

dp[i][j]:=(Aをi文字、Bをj文字使ってCの冒頭i+j文字の文字列を作れるか否か)のbool DP。

bool dp[201][201];

int main(){
  int n; cin >> n;
  int k = 0;
  while(n--){
    string a, b, c;
    cin >> a >> b >> c;
    
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;
    for(int i = 0; i <= (int)a.length(); i++){
      for(int j = 0; j <= (int)b.length(); j++){
	if(dp[i - 1][j] && (c[i + j - 1] == a[i - 1]))
	  dp[i][j] = true;
	if(dp[i][j - 1] && (c[i + j - 1] == b[j - 1]))
	  dp[i][j] = true;
      }
    }
    cout << "Data set " << ++k << ": " 
	 << (dp[a.length()][b.length()] ? "yes" : "no") << endl;
  }
  return 0;
}

うーん。まだまだ。