Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 22 的正整数被称为 Windy 数。 Windy 想知道，在 AA 和 BB 之间，包括 AA 和 BB，总共有多少个 Windy 数？ 输入格式 共一行，包含两个整数 AA 和 BB。 输出格式 输出一个整数，表示答案。 数据范围 1≤A≤B≤2×1091≤A≤B≤2×109 输入样例1： 1 10
输出样例1： 9
输入样例2： 25 50
输出样例2： 20
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 15; int f[N][10]; 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(k - j) >= 2) f[i][j] += f[i - 1][k]; } int dp(int n){ if (!n) return 0; vector<int> nums; while(n) nums.push_back(n % 10), n /= 10; int res = 0; int last = -2; for (int i = nums.size() - 1; i >= 0; i --){ int x = nums[i]; for (int j = i == nums.size() - 1; j < x; j ++) if (abs(j - last) >= 2) res += f[i + 1][j]; if (abs(x - last) >= 2) last = x; else break; if (!i) res ++; } for (int i = 1; i < nums.size(); i ++) for (int j = 1; j <= 9; j ++) res += f[i][j]; return res; } int main(){ init(); int l, r; scanf("%d%d", &l, &r); cout << dp(r) - dp(l - 1) << endl; return 0; }