AcWing 3710. 递进数字
原题链接
简单
作者:
飞舞
,
2021-06-25 13:40:22
,
所有人可见
,
阅读 250
昨天该开始学数位dp,就不bb方法了,存个代码供大家参考
思路一方面是递推组合数(不一定是组合数,大概是递推f[][],递推方法看f定义)
分类讨论数位
足位分类讨论最高位,最高位不取,下面是随便取
最高位取的话,就已经定了最高位,讨论次高位,这时相当于次高位是最高位,如果最好讨论到个位也成立,答案加1
不足位就是0-9随便选(最到位1-9)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 11;
int l,r;
int f[N][N];//i位数,最高位是j的方案数
void init(){
for(int i=0;i<=9;i++) f[1][i]=1;
for(int i=2;i<N;i++){
for(int j=0;j<=9;j++){
for(int k=0;k<=9;k++){
if(abs(j-k)==1)
f[i][j]+=f[i-1][k];
}
}
}
}
int dp(int n){
if(n<10) return 0;
vector<int> nums;
for(;n;n/=10) nums.push_back(n%10);
int res=0;
int last=0;
for(int i=nums.size()-1;i>=0;i--){
int x=nums[i];
for(int j = i == nums.size()-1; j<x ;j++){
if(i == nums.size()-1 || abs(j-last)==1)
res+=f[i+1][j];
}
if(abs(i == nums.size()-1) || abs(x-last)==1) last=x;
else break;
if(!i) res++;
}
for(int i=2;i<nums.size();i++){
for(int j=1;j<=9;j++){
res+=f[i][j];
}
}
return res;
}
int main()
{
init();
int T;cin>>T;
while(T--){
cin>>l>>r;
cout<<dp(r)-dp(l-1)<<endl;
}
return 0;
}