HDU 2089 不要62

本文主要是介绍HDU 2089 不要62，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：HDU 2089 不要62

题目大意：

题解：
很典型的数位\(dp\)题。
\(dp[i][0]\)：长度为\(i\)且第\(i+1\)位不是\(6\)的个数；
\(dp[i][1]\)：长度为\(i\)且第\(i+1\)位是\(6\)的个数。
从高位开始记忆化搜索即可。

#include <iostream>
using namespace std;

int dp[10][2], digit[10], n, m;

int dfs(int pos, bool preSix, bool limit) {
    if (!pos) {
        return 1;
    }
    if (!limit && dp[pos][preSix]) {
        return dp[pos][preSix];
    }
    int res = 0;
    for (int i = limit ? digit[pos] : 9; i >= 0; --i) {
        if (i == 4 || preSix && i == 2) {
            continue;
        }
        res += dfs(pos - 1, i == 6, limit && i == digit[pos]);
    }
    if (!limit) {
        dp[pos][preSix] = res;
    }
    return res;
}

int cal(int x) {
    int cnt = 0;
    while (x) {
        digit[++cnt] = x % 10;
        x /= 10;
    }
    return cnt;
}

int main() {
    while (cin >> n >> m && (n || m)) {
        cout << dfs(cal(m), 0, 1) - dfs(cal(n - 1), 0, 1) << endl;
    }
    return 0;
}

这篇关于HDU 2089 不要62的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！