L编码【noip模拟赛3】

发表于 | 分类于 ， | 阅读量 次

描述

Alice和Bob之间要进行秘密通信，他们正在讨论如何对信息进行加密：

Alice：“不如采用一种很简单的加密方式：’A’替换成1，’B’替换成2，„„，’Z’替换成26。”

Bob：“这种加密方式太傻了，Alice。如果我想要传送一个单词’BEAN’给你，它加密后就是25114。但你有很多种不同的方法来解密，从而得到许多单词！”

Alice：“你说的是没错，但是除了’BEAN’有意义以外，其他解密出来的’BEAAD’、

’YAAD’、’YAN’、’YKD’和’BEKD’都没有任何含义。”

Bob：“是的，但是同一个加密后的数字序列，可能的得到数以亿计的不同解密方案。”

Alice：“是吗？有这么多吗？”

你要帮助Bob编写一个程序，来说服Alice。对于一个加密后的数字序列，告诉她确切的解密方案数。

输入

有若干个加密后的数字序列，每行一个，行数不超过10，每行的数字数量不超过10000个。序列一定是符合要求的，例如没有先导的零和连续两个零等情况。数字间没有空格。一行一个零表示输入结束，这是不需要处理的。

输出

对于每个加密后的数字序列，输出一行。一个整数，表示解密的不同方案数。结果保证在32-bit带符号整数（longint）范围内。

输入样例 1

25114
1111111111
3333333333
0

输出样例 1

6 89
1

来源：
来自 <http://www.dingbacode.com/contest/19/problem/L>

题解：
Dp
第i（i>1）个数为0：
那么第i-1个数必定为1或2，这种情况唯一；
第i（i>1）个数为16：
如果第i-1个数为12，那么就有两种情况
否则情况唯一
第i（i>1）个数为7~9：
如果第i-1个数为1，那么就有两种情况
否则情况唯一

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
long long f[100005];
int main()
{
    char s[100005];
    while(cin>>s&&(s[0]-'0'))
    {
        memset(f,0,sizeof(f));

        f[0]=f[1]=1;
        long long chang=strlen(s);
        for(int i=1; i<chang; i++)
        {

            if(s[i]=='0') f[i+1]=f[i-2+1];
            else if(s[i]>='1'&&s[i]<='6')
            {
                if(s[i-1]>='1'&&s[i-1]<='2') f[i+1]=f[i-1+1]+f[i-2+1];
                else f[i+1]=f[i-1+1];
            }
            else
            {
                if(s[i-1]=='1')f[i+1]=f[i-1+1]+f[i-2+1];
                else f[i+1]=f[i-1+1];
            }


        }
        cout<<f[chang-1+1]<<endl;
    }

return 0;
}

​