算法提高课汇总

算法思路

本题思路与 AcWing 1081. 度的数量 类似: 按数位分类讨论, 其中左子树剩余数字任意选择,
一般用$DP$思路预处理方案数, 不同之处在于所求数字性质不同, 对应预处理$DP$思路不同.

$DP$分析

对于数字任意的不降数的个数, 用集合划分思路求解.

状态表示$f(i, j)$

• 集合: $i$位数且最高位为$j$的所有不降数.

• 属性: Count

状态计算

第$i$位固定为$j$, 我们可以以第$i - 1$位为划分依据. 设$i - 1$位为$k$, 则$k$为满足不降数其
范围为$j\le k\le 9$: $f(i, j) = \sum_{k} f(i - 1, k), j\le k\le 9$.

代码实现

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

using namespace std;

const int N = 11;

int f[N][N]; 

void init()
{
    for ( int j = 0; j <= 9; j ++ ) f[1][j] = 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 n)
{
    if ( !n )   return 1; //f[1][0], n = 0时nums为空 所以需要另外考虑

    vector<int> nums;
    while ( n ) nums.push_back( n % 10 ), n /= 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; //右子树不是不降数 可直接退出
        else    last = x;

        if ( !i )   res ++; //n自身也是不降数
    }
    return res;
}

int main()
{
    init();

    int l, r;
    while ( cin >> l >> r )     cout << dp(r) - dp(l - 1) << endl;

    return 0;
}