【第007题】题解及代码分享：数位DP经典模版题 [SCOI2009] windy 数

小码匠

发布于 2023-11-14 19:38:36

35200

代码可运行

文章被收录于专栏：小码匠和老码农小码匠和老码农

运行总次数：0

代码可运行

大家好！我是小码匠。

本周开始学习数位DP，今天分享的是一道经典的模版题。

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：7道
待完成：293道

已完成目标：

分类	算法	题目
算法基础	前缀和	【第001题】题解分享：湖南省选->激光炸弹
算法基础	差分	【第002题】题解分享：P4552 [Poetize6] IncDec Sequence
算法基础	高维前缀和	【第003题】题解及代码分享：CodeForces 165E Compatible Numbers
算法基础	尺取	【第004题】题解及代码分享：AtCoder ABC326-C
动态规划	动态规划	【第005题】题解及代码分享：AtCoder ABC326-D
算法基础	高维前缀和	【第006题】题解及代码分享：高位前缀和之AtCoder ARC100 - E Or Plus Max
动态规划	数位DP	【第007题】题解及代码分享：数位DP经典模版题 [SCOI2009] windy 数

前置知识

数位DP
- https://oi-wiki.org/dp/number/

题目描述

windy 定义了一种 windy 数。

题目描述

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

输入格式

输入只有一行两个整数，分别表示 a 和 b。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

1 10

输出 #1复制

输入 #2复制

25 50

输出 #2复制

说明/提示

数据规模与约定

对于全部的测试点，保证

1≤a≤b≤2×10^9

。

题解

补充样例数据

输入1

1 9

输出1

输入2

99 101

输出2

输入3

1 1

输出3

输入4

1 300

输出4

输入5

1 200000

输出5

思路

一道比较经典数位DP模版题，思路大家请参考洛谷官方
- https://www.luogu.com.cn/problem/solution/P2657

AC代码

#include <bits/stdc++.h>

using namespace std;

int dp[15][15], a[20], l = 0;

void init() {
    memset(dp, 0, sizeof(dp));

    dp[0][0] = 1;
    for (int i = 0; i <= 9; ++i) {
        dp[i][1] = 1;
    }
    for (int i = 2; i <= 10; ++i) {
        for (int j = 0; j <= 9; ++j) {
            for (int k = 0; k <= 9; ++k) {
                if (abs(j - k) >= 2) {
                    dp[j][i] += dp[k][i - 1];
                }
            }
        }
    }
}

int solve(int num) {
    int ans = 0;
    l = 0;
    memset(a, 0, sizeof(a));
    while (num > 0) {
        a[++l] = num % 10;
        num /= 10;
    }
    for (int i = 1; i <= 9; ++i) {
        for (int j = 1; j < l; ++j) {
            ans += dp[i][j];
        }
    }

    for (int i = 1; i < a[l]; ++i) {
        ans += dp[i][l];
    }
    for (int j = l - 1; j >= 1; --j) {
        for (int i = 0; i < a[j]; ++i) {
            if (abs(i - a[j + 1]) >= 2) {
                ans += dp[i][j];
            }
        }
        if (abs(a[j] - a[j + 1]) < 2) {
            break;
        }
    }


    return ans;
}

void best_coder() {
    int x, y;
    cin >> x >> y;
    init();
    int ans1 = solve(x);
    int ans2 = solve(y + 1);
    cout << ans2 - ans1;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}