windy数 [操作系统入门]

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

　　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>
usingnamespace std;
constint MAXN = 64;
int dp[MAXN][MAXN];
vector<int> dim;
int dfs(int x, int st, int lim) {
if (!x) return1;
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;
return0;
}

windy数

以上是 windy数 [操作系统入门] 的全部内容， 来源链接： utcz.com/z/518691.html

回到顶部