首页 > 代码库 > UESTC 250
UESTC 250
windy数
基本的数位DP,需要判断当前位是否为起始位。
#include <cstdio>#include <cmath>#include <cstring>using namespace std;#define D(x) xconst int MAX_DIGIT = 35;int n, m;int f[MAX_DIGIT];int memoize[MAX_DIGIT][2][2][15];void to_digits(int a){ for (int i = 0; i < MAX_DIGIT; i++) { f[i] = a % 10; a /= 10; }}int dfs(int digit, bool less, bool first, int last){ if (digit == -1) { return 1; } if (memoize[digit][less][first][last] != -1) { return memoize[digit][less][first][last]; } int limit = less ? 9 : f[digit]; int ret = 0; for (int i = 0; i <= limit; i++) { if (!first && abs(i - last) < 2) { continue; } ret += dfs(digit - 1, less || i < f[digit], first && i == 0, i); } memoize[digit][less][first][last] = ret; return ret;}int main(){ scanf("%d%d", &n, &m); n--; to_digits(n); memset(memoize, -1, sizeof(memoize)); int ans_n = dfs(32, false, true, 12); to_digits(m); memset(memoize, -1, sizeof(memoize)); int ans_m = dfs(32, false, true, 12); printf("%d\n", ans_m - ans_n); return 0;}
UESTC 250
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。