Classy Numbers （数位dp模板题）

Classy Numbers

题目大意：
给你l,r,让你找在这个闭区间内每位数字为0不超过3的个数，1<=l,r<=1e18

解题思路：
板子题，sta记录一下0的个数，>3的时候return 0 即可

Code：

#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define inf 9654234
#define ll long long
using namespace std;
ll dp[25][25];
int a[25];

ll dfs(int pos,int sta,bool limit){
	if(pos==0) return sta<=3;
	if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];  // 记忆化
	int up=limit?a[pos]:9;                             //限制
	ll ans=0;
    for(int i=0;i<=up;i++){
    	if(i) ans+=dfs(pos-1,sta+1,limit&&i==up);
		else ans+=dfs(pos-1,sta,limit&&i==up);
	}
	if(!limit) dp[pos][sta]=ans;
	return ans;
}

ll solve(ll x){
	int pos=0;
	while(x){
		a[++pos]=x%10;
		x/=10;
	}
	return dfs(pos,0,true);
}

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    while(T--){
    	ll a,b;
    	cin>>a>>b;
    	cout<<solve(b)-solve(a-1)<<"\n";
	}
	return 0;
}
 
 
 

本文地址：https://blog.csdn.net/weixin_43872264/article/details/107933538