首页 > 代码库 > windy数
windy数
题目链接
- 题意:
windy数:不含前导零且相邻两个数字之差至少为2的正整数。输入x、y,求[x, y]内的windy数的个数 - 分析:
简单的数位DP,注意前导零的影响
int f[20][10], bits[20]; int dfs(int pos, int pre, bool lmt, bool first) { if (pos == -1) return 1; if (!lmt && ~f[pos][pre]) return f[pos][pre]; int u = lmt ? bits[pos] : 9, ret = 0; for (int i = 0; i <= u; i++) { if (first || (!first && abs(pre - i) >= 2)) ret += dfs(pos - 1, i, lmt && i == u, first && !i); } return lmt || first ? ret : f[pos][pre] = ret; } int calc(int n) { CLR(f, -1); int len = 0; while (n) { bits[len++] = n % 10; n /= 10; } return dfs(len - 1, 0, true, true); } int main() { //freopen("0.txt", "r", stdin); int a, b; while (~RII(a, b)) { cout << calc(b) - calc(a - 1) << endl; } return 0; }
windy数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。