The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2033 Alphacode -动态规划

这道题的题意大概是这样的:给出一个字符串,如果将字母表中的26个字母依次映射成数字1-26,这样便形成一个密码,a cipher.学过密码学就知道,这是一个简单的替代密码不过似乎并不是那么好用,虽然加密的确很方便,可是解密就麻烦了,因为存在很多种解密的方法,所以本题就是要你求出一串数字究竟有多少种解密方法。

 

个人心得:这是我寒假做的最后几道题目的其中一道了,一拿到这道题目我就立刻想到了动态规划,呵呵,看来偶对dp开始有点感觉了;

解本题的关键在于将dp[i]装换成为dp[i-1]和dp[i-2]的关系

首先确定dp[1]和dp[2]的值 前者肯定等于1 而后者可能为2也可能为1 这个应该很容易判断出来

然后在判断i>=3的情况

如果ch[i]为字符‘0’ 那么dp[i]肯定等于dp[i-2].因为一个字符不可能被映射成0,它必须和前一个字符成为一个整体

如果不是字符零,那么看看这个字符与前一个字符是不是能构成一个小于等于26且大于0的数字

并且这个数字的第一位不是0,那么dp[i]=dp[i-1]+dp[i-2];

如果不是让面的两种情况 dp[i]=dp[i-1];

 

这个题目其实很容易想到,不过刚做的时候没有设出temp变量,只是规定两个数字的范围

'2'>=ch[i-1]>'0'&&ch[i]<='6'这样19就被和谐掉了所以一直调都不对最后才想到的 O(∩_∩)O~


Source Code

 

Problem: 2033  User: abilitytao

Memory: 272K  Time: 16MS

Language: C++  Result: Accepted


#include<iostream>

using namespace std;

 

 

long dp[50001];

char ch[50001];

 

 

int work(char a[])

{

    
int temp;

    
int len;

    len
=strlen(a);

    
int i;

    dp[
0]=1;

    temp
=(ch[0]-'0')*10+(ch[1]-'0');

    
if(temp>0&&temp<=26&&ch[1]!='0')

           dp[
1]=2;

    
else

           dp[
1]=1;

    
for(i=2;i<len;i++)

    {

           temp
=(ch[i-1]-'0')*10+(ch[i]-'0');

           
if(ch[i]=='0')

                  dp[i]
=dp[i-2];

          

           
else if(temp>0&&temp<=26&&ch[i-1]!='0')

                  dp[i]
=dp[i-1]+dp[i-2];

           
else

                  dp[i]
=dp[i-1];

    }

    
return dp[len-1];

}

 

int main ()

{

    
while(cin>>ch)

    {

           
if(ch[0]=='0')

                  
break;

           cout
<<work(ch)<<endl;

    }

    
return 0;

}


posted on 2009-02-19 13:09 abilitytao 阅读(1659) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理