代码

#include<bits/stdc++.h>

using namespace std;

int f[12][2][2][10][12][12];
string s;

int dfs(int nown,bool ei,bool fo,int lim,int lastn,int ls,int ns){
//	cout<<nown<<endl;
	if((~f[nown][ei][fo][lastn][ls][ns])&&!lim){
//		cout<<1<<endl;
		return f[nown][ei][fo][lastn][ls][ns];
	}
	if(nown==0) return (max(ls,ns)>=3);
	int minn=(nown==11?1:0),maxn=(lim?s[nown-1]-'0':9);
	int ans=0;
//	cout<<minn<<" "<<maxn<<endl;
	for(int i=minn;i<=maxn;i++){
		if((ei&&i==4)||(fo&&i==8)) continue;
		int nos=ns;
		if(i==lastn) nos++;
		else nos=0;
		ans+=dfs(nown-1,ei||(i==8),fo||(i==4),lim&&i==maxn,i,max(ls,nos),nos);
	}
	if(!lim) f[nown][ei][fo][lastn][ls][ns]=ans;
	return ans;
}

int main(){
	memset(f,-1,sizeof(f));
	string s1,s2;
	cin>>s1>>s2;
	reverse(s1.begin(),s1.end());
	reverse(s2.begin(),s2.end());
	s=s2;
	int cnt=dfs(11,0,0,1,0,0,0);
	memset(f,-1,sizeof(f));
//	cout<<cnt<<endl;
	s=s1;
	int cnt2=dfs(11,0,0,1,0,0,0);
//	cout<<cnt2<<endl;
	cout<<cnt-cnt2<<endl;
	return 0;
}

样例都没法过，算出来数字个数少了将近十倍

求大佬帮忙看看