[DP] poj 2033:Alphacode
1530 ワード
大体の問題:
一連の数を与えて、この一連の数がどれだけのアルファベット配列を構成するかを求めます.
大まかな考え方:
簡単DP、必ず0の場合に注意
一連の数を与えて、この一連の数がどれだけのアルファベット配列を構成するかを求めます.
大まかな考え方:
簡単DP、必ず0の場合に注意
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=50000;
char str[nMax];
long long dp[nMax];
int judge(int i){
if(str[i]+str[i-1]*10>=1&&str[i]+str[i-1]*10<=26){
return 1;
}
return 0;
}
int main(){
int n,i,j,k,len;
while(scanf("%s",str)&&str[0]!='0'){
len=strlen(str);
if(len==1){
printf("1
");
continue;
}
memset(dp,0,sizeof(dp));
for(i=0;i<len;i++)str[i]-='0';
dp[0]=1;
if(str[1]!=0){
if(judge(1))dp[1]=2;
else dp[1]=1;
}
else{
dp[1]=1;
}
for(i=2;i<len;i++){
if(str[i]==0){
if(judge(i))dp[i]=dp[i-2];
}
else{
if(judge(i)&&str[i]+str[i-1]*10>=11){
dp[i]=dp[i-1]+dp[i-2];
}
else{
dp[i]=dp[i-1];
}
}
}
printf("%lld
",dp[len-1]);
}
return 0;
}