SPOJ系列 —— SPOJ 394

SPOJ 394

题面这里都不给出，只讲基本思路。

这题是一个计数dp问题，是属于非常简单和明显的那种（经过省赛之后发现简单的题要能快速做）。

那么状态设计非常Simple:

dp(i) := 以 i 结尾的decode种类数

由于二十六个字母其最多只有两位因此最多存在两种转移方式：

• if 1 bit can : dp(i) += dp(i-1)
• if 2 bit can : dp(i) += dp(i-2)

之后就是简单的讨论下边界的问题。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

/* SPOJ 394  */
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    string x;

    while (std::cin >> x){
        if (x == "0") break;
        int n = x.length();

        // dp(i) := 当 i 结尾时有多少种不同的decode方式
        // dp(i) := dp(i-1) + dp(i-2)|if s[i-2,i] <= 26 && s[i-2] != 0
        vector<ll> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++ i){
            if (x[i - 1] != '0') dp[i] += dp[i - 1];
            if (i - 2 >= 0 && x[i - 2] != '0' && (x[i - 2] <= '1' or x[i - 2] == '2' && x[i - 1] <= '6'))
                dp[i] += dp[i - 2];
        }
        std::cout << dp[n] << "
";
    }

    return 0;
}