数字计数--数位dp

1.不考虑前导零

2.每一位计数，就是有点“数页码”的意思

P2602 [ZJOI2010] 数字计数 - 洛谷

相关题目：记得加上前导零

数页码--数位dp-CSDN博客

https://blog.csdn.net/2301_80422662/article/details/148160086?spm=1011.2124.3001.6209

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
ll n,k,m; 
vector<int> a,b;
ll dp[11][60];
ll dfs(int pos,int c,bool ismax,int id,vector<int> a,bool lead)///带考虑前导零的最全数位dp板子 
{if(pos==-1)///边界，return需要的答案，板子要改和灵活运用的地方 {return c;}int maxn;///选择上界 if(ismax) maxn=a[pos];else maxn=9;if(lead&&!ismax&&dp[pos][c]!=-1)///记忆化，lead=1即没有前导零 {return dp[pos][c];	} ll res=0;for(int i=0;i<=maxn;i++){if(i==id) res+=dfs(pos-1,c+(1&&(i||lead)),ismax&&i==maxn,id,a,lead||i);///考虑前导零就在lead这里写i||lead else res+=dfs(pos-1,c,ismax&&i==maxn,id,a,lead||i);}if(!ismax&&lead) return dp[pos][c]=res;///记忆化 return res;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;n--; while(n){a.push_back(n%10);n/=10;}while(m){b.push_back(m%10);m/=10;}int p1=a.size()-1,p2=b.size()-1;for(int i=0;i<=9;i++){memset(dp,-1,sizeof(dp));ll a2=dfs(p2,0,true,i,b,0);memset(dp,-1,sizeof(dp));ll a1=dfs(p1,0,true,i,a,0);cout<<a2-a1<<" ";	}return 0;
}