欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

相关标签: dp 数位dp