CQOI2016*

数位DP

不必算出所有状态，多用

记忆化搜索实现

具体看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
int num[12],f[11][11][11][2][2][2][2];
int dfs(int p,int a,int b,bool c,bool d,bool _4,bool _8){
	//当前枚举到哪 p+1位是多少 p+2位是多少 是否出现过连续3个相同数字 是否卡满 4是否出现过 8是否出现过 
	if(_4&&_8)return 0;
	if(p<=0)return c;
	if(f[p][a][b][c][d][_4][_8]!=-1)return f[p][a][b][c][d][_4][_8];
	int ret=0,lim=(!d?num[p]:9);
	for(int i=0;i<=lim;i++)
		ret+=dfs(p-1,i,a,c||(i==b&&i==a),d||i<lim,_4||i==4,_8||i==8);
	return f[p][a][b][c][d][_4][_8]=ret; 
}
inline int solve(int n){
	if(n<1e10)return 0;
	memset(f,-1,sizeof(f));
	int len=0,ret=0;
	while(n){
		num[++len]=n%10;
		n/=10;
	}
	for(int i=1;i<=num[len];i++)
		ret+=dfs(10,i,0,0,i<num[len],i==4,i==8);
	return ret;
}
signed main(){
	int l=read(),r=read();
	cout<<solve(r)-solve(l-1); 
	return (0-0);
}