[DP] poj 2033：Alphacode

大致题意：

    给出一串数，求出这串数可能组成多少种字母排列。

 

大致思路：

    简单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\n");
            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\n",dp[len-1]);
    }
    return 0;
}