AcWing 1083. Windy数
原题链接
中等
作者:
竹鼠不会咕
,
2020-02-03 20:18:51
,
所有人可见
,
阅读 1041
#include<bits/stdc++.h>
#define LL long long
#define INIT(a,b) memset(a,b,sizeof(a))
const int MAX=0x7fffffff;
const int MIN=-MAX;
const int INF=0x3f3f3f3f;
using namespace std;
int n,m;
int num[10],f[10][20][2];
int dfs(int len,int pre,bool limit,int lead){
if(!len) return 1;
if(!limit && ~f[len][pre][lead]) return f[len][pre][lead];
int up=limit?num[len]:9;
int ans=0;
for(int i=0;i<=up;i++){
if(lead || abs(pre-i)>=2)
ans += dfs(len-1, i, limit && i==up, lead && !i);
}
return limit? ans: f[len][pre][lead] = ans;
}
int solve(int n){
memset(f,-1,sizeof(f));
int k=0;
while(n){
num[++k]=n%10;
n/=10;
}
return dfs(k,-2,1,1);
}
int main(){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",solve(b) - solve(a-1));
return 0;
}