POJ 2033 Alphacode
問題
アルファベット大文字からなる平文に対し、A=1、B=2、…、Z=26と置き換える暗号化を行う。この暗号文は一意に復号化できない可能性がある。暗号文が与えられるので何通りの復号化があるか求めよ。
やりかた
DP。
dp[i]:=(i桁目までの復号化パターン数)とすると、今見ている桁だけ使った置換と、一つ前の桁も使った置換がありうるのでそれらの和になる。
dp[i + 1] = dp[i] + dp[i - 1]
ただし、今見ている桁が0の場合と、一つ前の桁が0の場合は例外なので注意。
以下ソース。
int main(int argc, char **argv){ string s; while(cin >> s){ if(s == "0") break; ll dp[1000000]; FILL(dp, 0); dp[0] = 1; for(int i = 0; i < s.size(); i++){ //今見ている桁だけ使った置換 if(s[i] != '0') dp[i + 1] += dp[i]; //一つ前の桁も使った置換が可能な場合 if(i - 1 >= 0 && (s[i - 1] - '0' != 0) && (s[i] - '0') + 10 * (s[i - 1] - '0') <= 26) dp[i + 1] += dp[i - 1]; } cout << dp[s.size()] << endl; } return 0; }
Get up! 明日のSUPER ST@R!