Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。
Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？
输入格式
共一行，包含两个整数 A 和 B。
输出格式
输出一个整数，表示答案。
数据范围
1≤A≤B≤2×109
输入样例1：
1 10
输出样例1：
9
输入样例2：
25 50
输出样例2：
20
#include<bits/stdc++.h>
using namespace std;
const int N = 11;
int f[N][10];
void init(){
for(int i = 0;i < 10;i ++)f[1][i] = 1;
for(int i = 2;i < N;i ++){
for(int j = 0;j < 10;j ++){
for(int k = 0;k < 10;k ++){
if(abs(j - k) >= 2)f[i][j] += f[i - 1][k];
}
}
}
}
int dp(int a){
if(!a)return 0;
vector<int>nums;
while(a)nums.push_back(a % 10),a /= 10;
int res = 0,last = -2;
for(int i = nums.size() - 1;i >= 0;i --){
int x = nums[i];
int l = (i == nums.size() - 1 ? 1 : 0);
for(int j = l;j < x;j ++){
if(abs(last - j) >= 2)res += f[i + 1][j];
}
if(i != nums.size() - 1 && abs(last - x) < 2)break;
last = x;
if(!i)res ++;
}
for(int i = nums.size() - 1;i >= 1;i --){
for(int j = 1;j < 10;j ++)res += f[i][j];
}
return res;
}
int main(){
init();
int l,r;
cin>>l>>r;
cout<<(dp(r) - dp(l - 1))<<endl;
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168582.html原文链接：https://javaforall.net
