windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道, 在A和B之间,包括A和B,总共有多少个windy数?\(1 \le A \le B \le 2000000000\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A,B;
int k[20],pos;//存数字各位
ll dp[20][10];//第i位为j的数字个数(不能大小限制)
/*
pos : 当前考虑的第pos位,例如十进制数12345,5为第0位
pre : 当前位的前一位的数字
lead : 是否有前导0,比如之前枚举的两位 00xxx,在枚举3位时是有前导0的。
limit : 是否有大小限制,比如枚举了12xxx,在枚举3位时最大枚举到3
*/
ll dfs(int pos,int pre,bool lead,bool limit){
if(pos == -1) return 1;
if(!limit && !lead && dp[pos][pre])return dp[pos][pre];
int up = limit ? k[pos] : 9;//确定枚举上界
ll res = 0;
for(int i=0;i<=up;i++){
if(lead){
if(i == 0){
res += dfs(pos-1,0,true,false);
}
else{
res += dfs(pos-1,i,false,limit && i == k[pos]);
}
}else{
if(abs(i-pre) < 2)continue;
res += dfs(pos-1,i,false,limit && i == k[pos]);
}
}
if(!limit && !lead)dp[pos][pre] = res;
return res;
}
ll solve(ll x){
int pos = 0;
while(x){
k[pos++] = x % 10;
x /= 10;
}
return dfs(pos-1,0,true,true);
}
int main(){
scanf("%lld%lld",&A,&B);
printf("%lld\n",solve(B) - solve(A-1));
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章