Classy Numbers (数位dp模板题)
程序员文章站
2022-07-06 13:37:02
Classy Numbers 题目大意:给你l,r,让你找在这个闭区间内每位数字为0不超过3的个数,1<=l,r<=1e18解题思路:板子题,sta记录一下0的个数,>3的时候return 0 即可Code:#include #include #include#include #include #include <...
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