Windy数

数位dp 无前导0 T3

题目描述

P2657 [SCOI2009] windy 数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数？

输入格式

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

输出格式

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

输入输出样例

输入

1 10

输出

9

数据规模与约定

对于全部的测试点，保证 $1\le a\le b\le 2\times 10^{9}1\le a\le b\le 2\times 109$。

思路

先画出数位树图： 以上是最高位不为0的情况, 最后还需要加上最高位为0时的情况, 所有数都成立。

代码

const int N = 11;
int f[N][N];
 
void init()
{
    for (int i = 0; i <= 9; i++)
        f[1][i] = 1;
    for (int i = 2; i < N; i++)
        for (int j = 0; j <= 9; j++)
            for (int k = 0; k <= 9; k++)
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}
 
int dp(int num)
{
    if (!num)
        return 0;
 
    vector<int> nums;
    while (num)
        nums.push_back(num % 10), num /= 10;
 
    int res = 0;
    int last = -3;
    for (int i = nums.size() - 1; i >= 0; i--)
    {
        int x = nums[i];
        for (int j = i == nums.size() - 1; j < x; j++)
        {
            if (abs(j - last) >= 2)
                res += f[i + 1][j];
        }
 
        if (abs(last - x) >= 2)
            last = x;
        else
            break;
 
        if (!i)
            res++;
    }
 
    for (int i = 1; i <= nums.size() - 1; i++)
        for (int j = 1; j <= 9; j++)
            res += f[i][j];
 
    return res;
}
 
int main()
{
    init();
    int a, b;
    cin >> a >> b;
    // cout << dp(a) << " " << dp(b) << endl;
    cout << dp(b) - dp(a - 1);
    return 0;
}