不要62-数位DP

Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了

Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100
0 0

Sample Output

80

题解

这道题是标准的数位DP模板

对于类似于在某个范围（a, b）内，存在多少个数字满足条件A（条件A通常都只是与这个数的数字组成有关而与其自身的性质无关），这种题目就是标准的数位DP

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-11-05 19:35:07
 * @Description: 不要62
 * @Website: https://grimoire.cn
 * @Copyright: 2020 Mr.Sen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;

int num[20], mem[20][2];
// num 用于储存初始化后的数字，mem用来记忆化搜索

typedef long long ll;

int dfs(int pos, int pre, bool limit, bool sta)
{
    // pos 当前搜索的数位
    // pre 当前搜索数位之前的值
    // limit ：
    // 例如：127， 当我们在搜索十位的时候，此时我们不能让各位超过7，因为这个数字最大也才127
    // 那么此时我们就计 limit = 1 表示搜索有上限 反之就是没有上限，可以搜索到9
    // sta 表示当前位是否为6
    
    if (pos == -1) return 1;
    if (!limit && mem[pos][sta]) return mem[pos][sta];

    int up = limit? num[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; i++)
    {
        if (pre == 6 && i == 2) continue;
        if (i == 4) continue;

        ans += dfs(pos-1, i, limit && num[pos] == i, i == 6); 
    }
    if (!limit) mem[pos][sta] = ans;
    return ans;
}

int init(int number)
{
    // 预处理
    int len = 0;
    while (number)
    {
        num[len++] = number % 10;
        number /= 10;
    }
    return dfs(len-1, -1, 1, 0);
}

int main()
{
    int a, b;
    while (cin >> a >> b)
    {
        if (a == b && a == 0)
        {
            return 0;
        }
        cout << init(b) - init(a-1) << endl;
        memset(mem, 0, sizeof(mem));
    }
    
    return 0;
}