菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
145
0

windy数

原创
05/13 14:22
阅读数 42217

题目链接

  • 题意:
    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 && !first && ~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; }



发表评论

0/200
145 点赞
0 评论
收藏