数字游戏

原题链接

数位DP

题目描述：计算[l,r]区间中的非下降数的个数
不降数：从高位到低位上各位数字呈非下降关系：如123，446

直接上代码

Code

#include <iostream>
#include <cstring>
#include <vector>

const int N = 15;

// f[i][j]表示共有i位，且最高位位j的数的个数
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 = j; k <= 9; k ++ )
                f[i][j] += f[i - 1][k];
}

int cal(int n) {
    if (!n) return 1;
    std::vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;
    
    int res = 0, pre = 0; // pre记录上一位数是几
    for (int i = nums.size() - 1; i >= 0; i -- ) {
        int x = nums[i];
        // 左分支，当然不能从0开始，要大于等于上一个数才可以
        // 此时方案数就是i+1位，最高位为j
        for (int j = pre; j < x; j ++ ) res += f[i + 1][j];
        // x<pre表示当前节点不存在右分支，直接break
        if (x < pre) break;
        pre = x; // 更新上一个数
        // 如果走到最后一个数，说明n本身就是个非下降数，合法方案数加1
        if (!i) res ++ ; 
    }
    
    return res;
}

int main() {
    init();
    
    int l, r;
    while (std::cin >> l >> r) std::cout << cal(r) - cal(l - 1) << '\n';
    return 0;
}