PKU 3073 Spam

http://poj.org/problem?id=3073
ある文字列が与えられる。
これをスパム語に変換したあと、それを復元するのに何通りの解釈が出来るかを答えろというような問題。

動的計画法。
前におもいっきり似た問題を解いた記憶があります。

string ctos[]={"4",
               "|3",
               "(",
               "|)",
               "3",
               "|=",
               "6",
               "#",
               "|",
               "_|",
               "|<",
               "|_",
               "|\\/|",
               "|\\|",
               "0",
               "|0",
               "(,)",
               "|?",
               "5",
               "7",
               "|_|",
               "\\/",
               "\\/\\/",
               "><",
               "-/",
               "2",
};

int dp[500];

main(){
  string in;
  set<string>app;
  rep(i,26)app.insert(ctos[i]);
  while(cin>>in,in!="end"){
    string str;
    rep(i,SZ(in))str+=ctos[in[i]-'A'];
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    rep(i,SZ(str)){
      for(int j=1;j<=4;++j){
        if(1+i-j<0)break;
        if(app.count(str.substr(1+i-j,j)))dp[i+1]+=dp[1+i-j];
      }
    }
    cout<<dp[SZ(str)]<<endl;
  }
}