DP

苦手。とりあえず、典型問題を解いて慣れていきたい。
ということで、練習問題。

• C.Welcome to Code Jam

文字列が与えられ、そのなかで「welcome to code jam」という文字がいくつ作れるか。
解説が載ってたので、そのとおりにやってみた。

(文字列の長さ)x(19パターン)の配列を用意しておいて、そこに入れていく。19パターンは「w」「we」「wel」...「welcome to code jam」。配列は、文字列のi番目までにそれぞれのパターンがいくつあるか。例えば、i番目の文字が"l"ならば、(i-1番目での「wel」の個数)＋(i-1番目での「we」の個数)を(i番目の「wel」の個数)にする。違う文字なら(i-1番目の「wel」の個数)を(i番目の「wel」の個数)にする。

#include <iostream>
using namespace std;

int dp[500][19];
string pat = "welcome to code jam";

void show(int num){
  num=num%10000;
  cout << num/1000;
  num=num%1000;
  cout << num/100;
  num=num%100;
  cout << num/10;
  num=num%10;
  cout << num << endl;
}

void calc(string str){
  for(int i=0; i<500; i++) for(int j=0; j<19; j++) dp[i][j] = 0;

  for(int i=0; i<str.length(); i++) for(int j=0; j<19; j++){
    if(i>=1) dp[i][j] = dp[i-1][j];
    if(str[i]==pat[j]){
      if(j==0) dp[i][j]++;
      if(i-1>=0 && j-1>=0) dp[i][j] = (dp[i][j] + dp[i-1][j-1])%10000;
    }
  }
  /*
  for(int j=0; j<19; j++){
    for(int i=0; i<str.length(); i++){
      cout << dp[i][j];
    }
    cout << endl;
  }
  */


  show(dp[str.length()-1][18]);
}

int main(){
  string str;
  int n;
  cin >> n; cin.get();
  for(int i=0; i<n; i++){
    getline(cin, str);
    cout << "Case #" << i+1 << ": ";
    calc(str);
  }
  return 0;
}