数位DP

概念

数位DP往往都是这样的题型，给定一个闭区间[ l , r ] [l,r][l,r]，让你求这个区间中满足某种条件的数的总数。而这个区间可能很大

其他

细节都在代码里

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N = 63;
ll dp[N][N],a[N];



// 当前是第几位 //  （去掉前导零）有几个数字 // 有没有前导零 // 目前这意味是否到达限制（即:前面的数都取到了最大）

ll dfs(ll pos,ll num,bool lead,bool limit){
	ll sum = 0;
	if(pos == 0) return num;
	//加记忆化，且仅存在于没有前导零和没有限制的时候
	if(!lead && !limit && dp[pos][num]!=-1) return dp[pos][num];
	//是否存在限制
	int up = (limit?a[pos]:9);
	for(int i = 0;i<=up;i++){
		//有前导零
		if(i == 0 && lead) sum+=dfs(pos-1,num,true,(limit && i == up));
		else if(i == 0) sum+=dfs(pos-1,num+1,false,(limit && i == up));
		else if(i!=0) sum+=dfs(pos-1,num,false,(limit && i == up));	
	}
	//   到第几位  /   有几个数
	//记忆化 
	//没有前导零 // 没有限制
	if(!lead && !limit) dp[pos][num] = sum;
	return sum;
}


ll js(ll x){
	if(x<0) return 0;
	if(x == 0) return 1;
	ll len = 0;
	//拆分这个数
	while(x){
		a[++len] = x%10;
		x/=10;
	}
	memset(dp,-1,sizeof dp);
	return dfs(len,0,true,true);
}

void solve(){
	ll l,r;
	while(scanf("%lld%lld",&l,&r)!=EOF){
		if(l<0 && r<0) return;
		if(l == 0 && r == 0) cout<<1<<endl;
		else if(l == 0) cout<<js(r)+1<<endl;
		// 前缀和的思想
		else cout<<js(r)-js(l-1)<<endl;
	} 
}

int main(){
	solve();
	return 0;
}