AcWing 1085. 不要62

杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。

杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有 4或62的号码。
例如：62315,73418,88914都属于不吉利号码。
但是，61152虽然含有 6和 2，但不是连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照号区间 [n,m]，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

输入格式
输入包含多组测试数据，每组数据占一行。

每组数据包含一个整数对 n和 m。

当输入一行为“0 0”时，表示输入结束。

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

数据范围
1≤n≤m≤10^9

1 100
0 0

80

#include<bits/stdc++.h>

using namespace std;

const int N = 35, M = 10;

int f[N][M];//i位 最高位是j 

//预处理
void init()
{
    //处理单位数
    for(int i=0;i<=9;i++) 
        if(i!=4)
            f[1][i]=1;

    //处理多位数
    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
        {
            if(j==4) continue;
            for(int k=0;k<=9;k++)
            {
                if(k==4||j==6&&k==2) continue;
                f[i][j]+=f[i-1][k];
            }
        }
}

// 0 ～ n 中符合条件的数
int dp(int n)
{
    if(!n) return 1;

    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n/=10;
    }

    int res=0,last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        //左子树 
        for(int j=0;j<x;j++)
        {
            if(j==4||last==6&&j==2) continue;
            res+=f[i+1][j];
        }

        //右子树不满足条件时（剪枝） 
        if(x==4||last==6&&x==2) break;
        //否则更新last 
        last=x;

        if(!i) res++; //当前数本身就符合条件
    }

    return res;
}

int main()
{
    init();

    int l,r;

    while(cin>>l>>r,l||r) cout<<dp(r)-dp(l-1)<<endl;

    return 0;
}