记忆化时不能有最高位限制,所以要加上!flag
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int num[13],cnt;
ll L,R;
ll dp[12][10][10][2][2][2];//从高位到低位搜到第i位,上一位选j,上上位选k,是否出现过4,是否出现过8,是否有三个连续的数,是否贴上界
ll dfs(int len,int la,int lla,bool f,bool e,bool con,bool flag)//长度,上位,上上位,是否有4,是否有8,是否有三连,是否贴上界
{
if (e&&f) return 0;
if (!len) return con;
if (!flag&&~dp[len][la][lla][f][e][con]) return dp[len][la][lla][f][e][con];
ll res=0;
for (int i=((len==11)?1:0);i<=9;i++)
{
if ((i<=num[len] || !flag))
res+=dfs(len-1,i,la,(i==4)||f,(i==8)||e,con||(i==la&&i==lla),flag&(i==num[len]));
}
if(!flag)
dp[len][la][lla][f][e][con]=res;
return res;
}
ll solve(ll x)
{
if (x<1e10)
return 0;
cnt=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
memset(dp,-1,sizeof(dp));
return dfs(11,0,0,0,0,0,1);
}
int main()
{
scanf("%lld%lld",&L,&R);
ll ans;
ans=solve(R);
ans-=solve(L-1);
printf("%lld",ans);
}
```
by Y_X_C @ 2023-10-27 20:32:09