之前暑假的时候找过模板来着…好像当时不是很懂那个模板…以至于之后就忘了要怎么写了…现在换了一种数位dp的写法…还是这种写法好懂呀…

https://www.cnblogs.com/wenruo/p/4725005.html

以不要62这道题为例：

1⃣️预处理出来dp(i)(j)：i位j为首数字的数字里有多少上牌号
如j=4时：dp(i)(j)=0
j!=4时：

2⃣️分离数位

比如52431,ans=sum{dp(5)(k),0<=k<=4}+sum{dp(4)(k),0<=k<=1}，到第三位4的时候，由于不能有4，所以就可以break，相当于处理完4的时候，前三位要固定好，打算处理3的时候就是52400～52420了，这些都是不符合条件的。
因为for(int j=0;j<d[i];j++)，所以这里处理出来的是[0,n)中符合要求的个数。

完整代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MOD 1000000007
usingnamespacestd;
int dp[10][10];//i位j为首数字的数字里有多少上牌号
int d[10];
void init()
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=7;i++)
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
                if(j!=4&&!(j==6&&k==2))
                    dp[i][j]+=dp[i-1][k];
            //printf("dp[%d][%d]:%d\n",i,j,dp[i][j]);
        }
}
int solve(int n)//处理出[0,n)
{
    int len=0;
    while(n)
    {
        d[++len]=n%10;
        n=n/10;
    }
    d[len+1]=0;//处理n=0的情况
    int ans=0;
    for(int i=len;i>=1;i--)
    {
        for(int j=0;j<d[i];j++)
            if(j!=4&&!(j==2&&d[i+1]==6))
            {
                ans+=dp[i][j];
            }
        if(d[i]==4||(d[i]==2&&d[i+1]==6))break;
        //这里不是d[i]==6&&d[i-1]==2的原因是：比如1621，难道处理到6之后，1600 1610里面就没有号牌了吗，所以要到最后一位。
        //1000 1100 1200 1300 1400 1500 1600 1610
    }
    return ans;
}
int main()
{
    init();
    int l,r;
    while(scanf("%d%d",&l,&r)!=EOF)
    {
        if(l==0&&r==0)break;
        printf("%d\n",solve(r+1)-solve(l));
    }
    return 0;
}