hdu 2089 不要62 (数位dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089

数位dp模板题

数位dp学习博客：https://www.sohu.com/a/273617542_100201031

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 100;

int l, r, len;
int a[maxn];
int dp[maxn][10][2];

int dfs(int pos, int pre, int is,int lead, int lim){ 
	if(pos == len + 1) return is; 
	if(dp[pos][pre][is] != -1 && (!lead) && (!lim)) return dp[pos][pre][is];
	
	int res = 0;
	int limit = lim ? a[len - pos + 1] : 9;
	for(int i = 0 ; i <= limit ; ++i){
		int flag = 1;
		if(i == 4 || (i == 2 && pre == 6)) flag = 0;
		if((!i) && lead) res += dfs(pos + 1, 0, 1, 1, lim && (i == limit));
		else if(i && lead) res += dfs(pos + 1, i, is && flag, 0, lim && (i == limit));
		else res += dfs(pos + 1, i, is && flag, 0, lim && (i == limit));
	}
	return ((!lim) && (!lead)) ? dp[pos][pre][is] = res : res;
}

int part(int x){
	len = 0;
	while(x){
		a[++len] = x % 10; x /= 10;
	}
	memset(dp, -1, sizeof(dp));
	return dfs(1, 0, 1, 1, 1);
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	while(1){
		l = read(), r = read();
		
		if(l == 0 && r == 0) break;
		
		printf("%d
", part(r) - part(l - 1));	
	}
	
	return 0;
}