$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. f[i][j] 表示共有 i 位数且最高位是 j 的吉利数，last 表示上一位数
2. dp(n) 表示 0 ～ n 中符合条件的数
3. 首先预处理，公式：f[i][j] += f[i - 1][k]，但需符合条件 j != 4 && !(j == 6 && k == 2)
4. 枚举每一位，res += f[i + 1][j]，但需符合条件 j != 4 && !(last == 6 && j == 2)
5. 处理完所有左分支后，处理右分支，符合条件则 res ++

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 35, M = 10;

int f[N][M];

//预处理
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=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;
}