数字游戏

题目描述

#10164. 「一本通 5.3 例 2」数字游戏 - 题目 - LibreOJ (loj.ac) 科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 $123$，$446$。现在大家决定玩一个游戏，指定一个整数闭区间 $[a,b]$，问这个区间内有多少个不降数。

输入格式

有多组测试数据。每组只含两个数字 $a,b$，意义如题目描述。

输出格式

每行给出一个测试数据的答案，即 $[a,b]$ 之间有多少不降数。

样例

输入

1 9
1 19

输出

9
18

数据范围与提示

对于全部数据，$1\le a\le b\le 2^{31}-1$。

思路

求区间内数量可以转化为求 dp(r) - dp(l-1)。 对于一个数N: 48124, 求小于等于该数的不降数数量。沿用上一题的思路：

代码

const int N = 33;
int f[N][10];
 
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 = j; k <= 9; k++)
                f[i][j] += f[i - 1][k];
}
 
int dp(int num)
{
    if (!num)
        return 1;
 
    vector<int> nums;
    while (num)
        nums.push_back(num % 10), num /= 10;
 
    int res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; i--)
    {
        int x = nums[i];
        for (int j = last; j < x; j++)
            res += f[i + 1][j];
        if (x < last)
            break;
        last = x;
        if (!i)
            res++;
    }
 
    return res;
}
 
int main()
{
    init();
    int a, b;
    while (scanf("%d%d", &a, &b) != EOF)
    {
        cout << dp(b) - dp(a - 1) << endl;
    }
    return 0;
}