送分了QAQ 题解

数位dp，如果有4直接标记状态2，如果有3标记状态1，如果有8并且状态为1，标记状态2。
依次枚举数位，如果发现数字一定合法（该位小于x，后面的位上的数可以任意填），并且f数组已经算过，可以直接返回。

//注意记忆化 如果后面可以任意填了并且已经算过就直接返回
if(flag&&f[pos][st]!=-1) return f[pos][st];
//后面可以任意填了，就在对应位置记录一下，提高时间效率
if(flag) f[pos][st]=ans;

以下是加了这两句话和没加这两句话的对比：

#include <bits/stdc++.h>
using namespace std;
int f[9][3];
int a[9];
int dp(int pos,int st,bool flag)
{
    if(pos==0) return st==2;
    if(flag&&f[pos][st]!=-1) return f[pos][st];
    int x=flag?9:a[pos];
    int ans=0;
    for(int i=0;i<=x;i++)
    {
        if(i==4||st==2||(i==8&&st==1))
            ans+=dp(pos-1,2,flag||i<x);
        else if(i==3)
            ans+=dp(pos-1,1,flag||i<x);
        else ans+=dp(pos-1,0,flag||i<x);
    }
    if(flag) f[pos][st]=ans;
    return ans;
}
int cul(int x)
{
    memset(a,0,sizeof(a));
    int pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dp(pos,0,false);
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        memset(f,-1,sizeof(f));
        printf("%d\n",cul(m)-cul(n-1));
    }
}