题目链接
正式迈入了数位 DP 的大门......
心情激动
(看我立个 flag,我如果专攻数位 DP 的话,到 wc 之前就会有秒数位 DP 蓝题的能力)
数位 DP 讲解 链接
讲的非常详细,良心博客.比我写的博客加在一起还要良心.
设 f[i][j] 表示第 i 位,上一位是 j 的方案数.
按照那篇博客的指示枚举即可,注意判断前导零.
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline long long read(){
long long num=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
num=num*10+ch-'0';
ch=getchar();
}
return num*f;
}
int f[22][12]; // 位数,上一位是什么
int d[30];
int dfs(int pos,bool limit,bool lead,int pre){
if(pos==0) return 1;
if(limit==0&&lead==0&&f[pos][pre]!=-1) return f[pos][pre];
int up=limit==1?d[pos]:9;
int ans=0;
for(int i=0;i<=up;++i){
if(abs(i-pre)<2&&lead==0) continue;
ans+=dfs(pos-1,limit&&i==d[pos],lead&&i==0,i);
}
if(limit==0&&lead==0) f[pos][pre]=ans;
return ans;
}
int calc(int num){
int ret=num,len=0;
while(ret){
d[++len]=ret%10;
ret/=10;
}
return dfs(len,1,1,0);
}
int main(){
memset(f,-1,sizeof(f));
int a=read(),b=read();
printf("%d\n",calc(b)-calc(a-1));
return 0;
}
来源: http://www.bubuko.com/infodetail-2477008.html