首页 > 搜索 > DFS搜索 > HDU 1508 Alphacode-动态规划-[解题报告] C++
2013
12-12

HDU 1508 Alphacode-动态规划-[解题报告] C++

Alphacode

问题描述 :

Alice and Bob need to send secret messages to each other and are discussing ways to encode their messages:

Alice: "Let’s just use a very simple code: We’ll assign ‘A’ the code word 1, ‘B’ will be 2, and so on down to ‘Z’ being assigned 26.”
Bob: "That’s a stupid code, Alice. Suppose I send you the word ‘BEAN’ encoded as 25114. You could decode that in many different ways!”
Alice: "Sure you could, but what words would you get? Other than ‘BEAN’, you’d get ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ and ‘BEKD’. I think you would be able to figure out the correct decoding. And why would you send me the word ‘BEAN’ anyway?”
Bob: "OK, maybe that’s a bad example, but I bet you that if you got a string of length 500 there would be tons of different decodings and with that many you would find at least two different ones that would make sense.”
Alice: "How many different decodings?"
Bob: "Jillions!"

For some reason, Alice is still unconvinced by Bob’s argument, so she requires a program that will determine how many decodings there can be for a given string using her code.

输入:

Input will consist of multiple input sets. Each set will consist of a single line of digits representing a valid encryption (for example, no line will begin with a 0). There will be no spaces between the digits. An input line of ‘0’ will terminate the input and should not be processed

输出:

For each input set, output the number of possible decodings for the input string. All answers will be within the range of a long variable.

样例输入:

25114
1111111111
3333333333
0

样例输出:

6
89
1

Hint
Hint
It can be confirmed that no zero in the head and no trailing zeros in the integer. Please pay special notice on the position of zero.

题目中字符串的长度没有说清楚(也可能是我没看到),提交一直返回wa,改了好久。。。

简单的记忆化搜索。需要注意对于0的情况要特别处理。为了方便处理,我的字符串是从1输入的,在字符串的最后我又添加了一个1.

#include<stdio.h>
#include<string.h>
#define N 1000005
typedef long long LL;
char s[N];
int a[N],ln;
LL dp[N];
LL dfs(int x)
{
    if(x>=ln) return 1;
    if(dp[x]>0) return dp[x];
    if(a[x+1]!=0) dp[x]+=dfs(x+1);
	if(a[x]*10+a[x+1]<=26&&a[x+2]!=0) dp[x]+=dfs(x+2);
    return dp[x];
}
int main()
{
    while(gets(s+1))
    {
        if(s[1]=='0') break;
        ln=strlen(s+1);
		int i;
        for(i=1; i<=ln; i++) a[i]=s[i]-'0';
		a[i]=1;
        memset(dp,0,sizeof(dp));
        dp[1]=dfs(1);
        printf("%I64d\n",dp[1]);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/zizaimengzhongyue/article/details/12448235


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了