POJ 2033 Alphacode 解题报告

一、问题描述

 

二、解题思路

用sum[i]表示字符串str[i-(len-1)]可以解释成多少种，可以得到递推式：

Sum[i]=0 如果str[i]==’0’;

Sum[i]=1如果i==len or i==(len-1);

如果str[i]==’1’ or (str[i]==’2’ and str[i+1]<=’6’

     如果str[i+1]==’0’ sum[i]=sum[i+2];

     否则sum[i]=sum[i+2]+sum[i+1];

否则 sum[i]=sum[i+1];

采用递归的方式实现。

三、代码

 

#include<iostream>
using namespace std;
char str[50000];
int sum[50000];
int len;
int GetKind(int i)
{
    if(sum[i]!=0)
        return sum[i];
    if(str[i]=='0')
        return 0;        
    if(i==len || i==(len-1))
    {
        sum[i]=1;
        return sum[i];
    }
    else
    {
        if(str[i]=='1' || (str[i]=='2' && str[i+1]<='6'))
        {
            if(str[i+1]=='0')
            {
                sum[i]=GetKind(i+2);
            }
            else
            {                
                int a=GetKind(i+2);
                int b=GetKind(i+1);
                sum[i]=a+b;
            }
            return sum[i];
        }
        else
        {
            sum[i]=GetKind(i+1);
            return sum[i];
        }
    }
}
int main()
{
    while(scanf("%s",&str))
    {
        if(str[0]=='0')
            break;
        memset(sum,0,sizeof(sum));
        len=strlen(str);
        printf("%d\n",GetKind(0));
    }
    return 0;
}