数位dp

3555 Bomb

题意： 输出含49的数有几个

#include <cstdio>
#include <cstring>
using namespace std ; 
typedef long long ll ;
const int N = 20 ; 
ll digit[20] , dp[N][2] ; 
ll dfs(int len , bool is4 , bool limit){
	//is4记录上一位是不是4,limit判断所在位是否为上界 
	if (!len)	return 1 ; 
	if (!limit && dp[len][is4] != -1)	return dp[len][is4] ; //已经搜过了直接返回结果 （记忆化搜索）
	ll ans = 0 ; 
	int maxn = limit?digit[len]:9 ;  
	//如果当前位数为上界，则上界定为给定的数，如果不是则为9，
	//例如数为5123 那么千位的上界为5 百位的上界为1 十位的上界为2 个位的上界为3 
	for (int i = 0 ; i <= maxn ; ++ i){
		if (is4 && i == 9)		continue ; 
		ans += dfs(len-1,i==4,limit&&i==maxn) ;
		//limit&&i==maxn(如果当前位是上界并且要搜索的下一位是上界的话，那下一位要按上界有限制)
	}
	if (!limit)		dp[len][is4] = ans ; //如果不是上限的话记录下来
	return ans ; 
} 
ll solve(ll x){	//求不含49的数
	int len = 0 ;
	memset(digit,0,sizeof(digit)) ; 
	while(x){	//求各个位上的数字
		digit[++len] = x%10 ; 
		x /= 10 ; 
	}
	return dfs(len,false,true) ; 
}
int main(){
	int t ; 
	scanf ("%d",&t) ;
	memset(dp,-1,sizeof(dp)) ; 
	while(t--){
		ll n ;
		scanf ("%lld",&n) ;
		printf ("%lld\n",n+1-solve(n)) ;
	}	
	return 0 ; 
}
 

2089 不要62

题意： 给出区间 [ l , r ] 求区间之间不含62 和 4 的数字有几个

#include <cstdio>
#include <cstring>
using namespace std ; 
const int N = 30 ; 
int digit[N] , dp[N][2] ; 
int dfs(int pos , bool is6 , bool limit){
	if(pos==0)	return 1 ; 
	if(!limit && dp[pos][is6]!=-1)	return dp[pos][is6] ; 
	int ans = 0 ; 
	int maxn = limit?digit[pos]:9 ; 
	for(int i=0; i<=maxn ; ++i){
		if((is6&&i==2) || i==4)	continue ; 
		ans += dfs(pos-1,i==6,limit&&i==maxn) ; 
	}
	if(!limit)	dp[pos][is6] = ans ;
	return ans ; 
}
int solve(int n){
	memset(digit,0,sizeof(digit)) ; 
	int len = 0 ; 
	while(n){
		digit[++len] = n%10 ; 
		n /= 10 ;
	}
	return dfs(len,false,true) ;
}
int main(){
	int n , m ; 
	memset(dp,-1,sizeof(dp)) ;
	while(scanf("%d%d",&n,&m) && (n||m)){	 
		int a = solve(n-1) ; 
		int b = solve(m) ; 
		printf("%d\n",b-a) ;
	}	
	return 0 ; 
}