蓝桥练习题 数位递增数 引深（搜索剪枝vs枚举) 代码
#include <iostream>
#include <string.h>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
ll dfs(ll i,ll k, ll n){
ll res=0;
if(i==n){
return 9-k+1;
}
for(ll j=k;j<=9;j++){
res+=dfs(i+1,j,n);
}
return res;
}
ll dfs2(ll i,ll k, ll n, vector<int>& r2){
ll res=0;
if(i==n){
if(r2[i-1]>=k){
//cout<<"----"<<r2[i-1]-k+1<<endl;
return r2[i-1]-k+1;
}else{
//cout<<"+++"<<i<<" "<<k<<endl;
return 0;
}
}
for(ll j=k;j<=r2[i-1];j++){
if(j==r2[i-1]){
res+=dfs2(i+1,j,n,r2);
}else{
res+=dfs(i+1,j,n);
}
//cout<<j<<" "<<i+1<<" "<<n<<" "<<res<<endl;
}
return res;
}
int main(){
ll n,ans=0;
cin>>n;
vector<int> r,r2;
ll t=n;
while(t>0){
r.push_back(t%10);
t=t/10;
}
ll size=r.size();
for(ll i=0;i<size;i++){
r2.push_back(r[size-1-i]);
}
for(ll i=2;i<size;i++){
ans+=dfs(1,1,i);
}
ans+=dfs2(1,1,size,r2);
cout<<ans<<endl;
ans=0;
for(ll i=10;i<=n;i++){
ll k=i;
ll last=k%10;
k=k/10;
bool dec_flag=false;
while(k>0){
if(k%10>last){
dec_flag=true;
break;
}
last=k%10;
k=k/10;
}
if(!dec_flag){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
