最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

数位DP基础概念 指路：【数位DP基本概念+数位DP记忆化搜索】

题目描述

求整数区间 $[L, R]$ 内， 不降数 的个数

不降数：数位从高到低呈非下降关系（【例】：123，446）

分析

想了解 数位DP 基础概念的，可以看一下最上面我贴的链接，这里不会对 重复内容 进行额外讲解

同样是用 前缀和 思想，转化为求一个 前缀区间 的 数字个数，直接套 数位DP 模板

为了保证 从大到小 的 数位 上的 数字 构成一个 非下降 的 序列

这里 记忆化搜索 的 参数 $st$ 要记录 前一位数位的数字是什么

就是这么简单的一道题

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35;

int l, r;
int a[N], al;
int f[N][N];

int dp(int pos, int st, int op)
{
    if (!pos) return 1;
    if (!op && ~f[pos][st]) return f[pos][st];
    int res = 0, maxx = op ? a[pos] : 9;
    for (int i = st; i <= maxx; i ++ )
        res += dp(pos - 1, i, op && i == a[pos]);
    return op ? res : f[pos][st] = res;
}
int calc(int x)
{
    memset(f, -1, sizeof f); al = 0;
    for (; x; x /= 10) a[ ++ al] = x % 10;
    return dp(al, 0, 1);
}
int main()
{
    while (cin >> l >> r)
    {
        cout << calc(r) - calc(l - 1) << endl;
    }
    return 0;
}