PKU 2033-Alphacode

PKU

問題概要

アルファベットからなる文字列を'A'→1、'B'→2、……、'Z'→26のように数字に置換し、それを並べてエンコードすることを考える。(例：BZ→226)
復号方法は何通りあるのか答えよ

解法

DPにより解を求める

実装(C++)

#include <iostream>
#include <algorithm>
using namespace std;
string s;
typedef long long lli;

lli dp[1000001];
int main() {
	while(cin>>s){
		if(s=="0")break;
		fill(dp,dp+s.size()+1,0);
		dp[0]=1;
		for(int i=0;i<s.size();i++){
			if(s[i]!='0')dp[i+1]+=dp[i];
			if(i+2<=(int)s.size()){
				if(10*(s[i]-'0')+s[i+1]-'0'<=26&&10*(s[i]-'0')+s[i+1]-'0'>0&&s[i]!='0')
					dp[i+2]+=dp[i];
			}
		}
		cout<<dp[s.size()]<<endl;
	}
	return 0;
}