windy数 -云博客

windy数

# windos 2024-05-05 09:32 0 34 来源：云博客

　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

输入格式

　　包含两个整数，A B。

输出格式

　　一个整数

数据范围和提示

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

Sample Input

【输入样例一】1 10【输入样例二】25 50

Sample Output

【输出样例一】9【输出样例二】20

#include<bits/stdc++.h>using namespace std;const int MAXN = 64;int dp[MAXN][MAXN];vector<int> dim;int dfs(int x, int st, int lim) { if (!x) return 1; if (!lim && dp[x][st] != -1) return dp[x][st]; int up = lim ? dim[x] : 9, ret = 0; for (int i = 0; i <= up; i++) { if (abs(i - st) < 2) continue;//绝对值之差小于2不能选 if (st == 11 && i == 0)//前导零状态 ret += dfs(x - 1, 11, lim & (i == up)); else//正常状态 ret += dfs(x - 1, i, lim & (i == up)); } if (!lim) dp[x][st] = ret;//如果当前限制状态量为0 return ret;//返回当前答案}int solve(int x) { memset(dp, -1, sizeof(dp)); dim.clear(); dim.push_back(-1); while (x) { dim.push_back(x % 10); x /= 10; } return dfs(dim.size() - 1, 11, 1);//从最高位开始枚举，初始状态限制标记量标为1}int main() { int A, B; cin >> A >> B; cout << solve(B) - solve(A - 1) << endl; return 0;}