851 AlvinZH的鬼畜密码

思路

难题。动态规划。

先判断字符串是否合理（可翻译），然后分段处理，每一小段用动态规划求出解法数。

dp[i]：字符串str[0~i]的解法数。通过判断str[i]，不同情况下dp[i]求解情况不同。

在参考代码一中，助教使用了思路比较好理解的方法，同学们可以借助注释来理解。

其实不用这么复杂，划分啥的。直接整个一起dp就好。可能会有些不太好理解，具体参考参考代码二。

二者方法相同，效率也相同。

分析

• 坑一：解法数为0判别：①首字符为'0'；②不为"10"或"20"；
• 坑二：最终答案可能为long long；
• 坑三：分析最小问题，注意0只能和前面的组成一个，每种情况都要考虑字符是否为1。
• 坑四：分割字符串，各自算出解法数相乘。

本题弱化版请参考zoj 2202。

参考代码一

//

// Created by AlvinZH on 2017/9/18.

// Copyright (c) AlvinZH. All rights reserved.

//

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

long long dp[55];

bool isLegal(string s)

{

    if(s[0] == '0') return false;

    else

    {

        for(int i = 1; i < s.length(); i++)

        {

            if(s[i] == '0' && (s[i-1] < '1' || s[i-1] > '2'))

                return false;

            if(s[i] == '#' && s[i + 1] == '#')

                return false;

        }

    }

    return true;

}

long long solveStr(string s)

{

    int l = s.length();

    memset(dp,0,sizeof(dp));

    dp[0] = 1;

    for(int i = 1; i < l; i++)

    {

        if(s[i] == '0')//必须与前一数字结合

        {

            if(i == 1)//开头组成'10'或'20'

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

            else//非开头组成'10'或'20'

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

        }

        else

        {

            if((s[i-1] == '1' && s[i] <= '9') || (s[i-1] == '2' && s[i]<='6'))//可以与前一数字结合

            {

                if(i != 1)//非开头组成'11'~'19'、'21'~'26'

                    dp[i] = dp[i-1] + dp[i-2];//与前一数字不结合+结合

                else

                    dp[i] = dp[i-1] + 1;//与前一数字不结合+结合

            }

            else

                dp[i] = dp[i-1];//单独一个翻译

        }

    }

    return dp[l-1];

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    string s;

    while(cin >> s && s != "0")

    {

        if(isLegal(s))

        {

            int l = s.length();

            long long ans = 1;

            int start=0;

            for(int i = 0; i < l; i++)

            {

                if(s[i] == '#')

                {

                    ans = ans*solveStr(s.substr(start,i-start));

                    start=i+1;

                }

            }

            ans=ans*solveStr(s.substr(start,l-start));

            printf("%lld\n",ans);

        }

        else printf("0\n");

    }

}

参考代码二

#include <iostream>

#include <cstring>

using namespace std;

long long dp[55];

char A[55];

int main()

{

    while(~scanf("%s", A+1))

    {

        dp[0] = 1;

        int len = strlen(A+1);

        if(len == 1 && A[1] == '0') break;

        for (int i = 1; i <= len; ++i) {

            dp[i] = 0;

            if(A[i]=='#' && A[i-1]=='#') {

                dp[i] = 0;

                continue;

            }

            if(A[i]=='#') {

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

                continue;

            }

            if(A[i] != '0')

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

            if(i-2>=0 && A[i-1]!='#' && A[i-1] != '0' && (A[i-1]-'0')*10+(A[i]-'0')<=26)

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

        }

        printf("%lld\n",dp[len]);

    }

}