HDU 2089 不要62 数位DP模板题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089

参考博客：https://www.cnblogs.com/HDUjackyan/p/9142156.html

说明，上面这篇博客已经可以很清楚地理解这道题目所表现得意思了。我这里是上述博客中的第一题。

这道题目呢我目前已经知道怎么做了，但是我还不能很好地做到用文字表述出来，所以大家可以试着看看我的代码，我也是通过看上面那篇博客的代码理解数位DP的思想的。

我在上面博客的代码中做了一些精简，省略了一个多余的状态参数，代码如下：

#include <iostream>

#include <cstring>

using namespace std;

int a[20], dp[20][2];

/*

pos表示目前将要访问的位置

pre表示前一个值是不是6，因为这里涉及到62连数，所以我们在访问到后一位的时候要考虑前一位，这里pre就用于存储前一位

limit表示是不是在边界位置

*/

int dfs(int pos, int stat, bool limit) {

    if (pos == -1) return 1;

    if (!limit && dp[pos][stat] != -1) return dp[pos][stat];

    int up = limit ? a[pos] : 9;

    int tmp = 0;

    for (int i = 0; i <= up; i ++) {

        if (stat && i == 2) continue;

        if (i == 4) continue;

        tmp += dfs(pos-1, i==6, limit&&i==a[pos]);

    }

    if (!limit) dp[pos][stat] = tmp;

    return tmp;

}

int solve(int x) {

    int pos = 0;

    while (x) {

        a[pos++] = x % 10;

        x /= 10;

    }

    return dfs(pos-1, 0, true);

}

int main() {

    int l, r;

    while ((cin >> l >> r) && l+r) {

        memset(dp, -1, sizeof(dp));

        cout << solve(r) - solve(l-1) << endl;

    }

    return 0;

}

其中，

pos表示目前将要访问的位置
pre表示前一个值是不是6，因为这里涉及到62连数，所以我们在访问到后一位的时候要考虑前一位，这里pre就用于存储前一位
limit表示是不是在边界位置

学习链接：

https://www.luogu.org/blog/virus2017/shuweidp

巴特西

HDU 2089 不要62 数位DP模板题

最新文章

热门文章