PKU : 3073 - Spam
問題概要
http://poj.org/problem?id=3073
入力された文字列を, 問題文中の表に基づいて変換します.
この変換された文字列をさらにもとのアルファベットの文字列へ戻すためには, 複数通りの戻し方があります.
この戻し方は, 何パターンあるでしょうか.
アルゴリズム
dp[i] = i番目までの文字を使ったときのパターン数
のDPで解けます.
プログラム
string alpha[] = { "4", "|3", "(", "|)", "3", "|=", "6", "#", "|", "_|", "|<", "|_", "|\\/|", "|\\|", "0", "|0", "(,)", "|?", "5", "7", "|_|", "\\/", "\\/\\/", "><", "-/", "2" }; int main(void){ string ts; int dp[402]; while(cin>>ts,ts!="end"){ int m = ts.length(); string s; rep(i,m){ s += alpha[ts[i]-'A']; } int n = s.length(); memset(dp,0,sizeof(dp)); dp[0] = 1; rep(i,n){ string tmp; rep(len,4){ if(n <= i + len) break; tmp += s[i+len]; rep(j,26){ if(alpha[j] == tmp){ dp[i+len+1] += dp[i]; break; } } } } cout<<dp[n]<<endl; } }