AcWing 1082. 数字游戏

题目传送门

一、数位DP模板解法

#include 

using namespace std;
const int N = 20;

int a[N];    //数位分离的数组
int dp[N][N];//dp[pos][pre]表示当前第pos位,pre是指前一位是什么，这个因素制约了后面的取值个数

/**
 * 功能：统计[0~pos]之间答案
 * @param pos  当前枚举到的数位pos（搜索的深度）由高到低
 * @param pre  前一位是什么
 * @param limit  前几位的数字是否等于上界的前几位数字 op(0/1)（限制本次搜索的数位范围）
 * @return 方案数
 */
int dfs(int pos, int pre, bool limit) {
    //成功到达最后，就是贡献了1个方案
    if (pos == -1) return 1;
    //记忆化搜索，前提是不贴着上界（可以枚举满这一位所有的数字）
    //只有无限制、无前导零才算，不然都是未搜索完的情况
    if (!limit && ~dp[pos][pre]) return dp[pos][pre];
    //up表示能枚举的最高位数
    int res = 0, up = limit ? a[pos] : 9;
    for (int i = pre; i <= up; i++)//尝试填充每一个可能的数字
        res += dfs(pos - 1, i, limit && i == a[pos]);
    //如果不受限制，则记录下来提供下次使用；如果受限制，则一把一利索
    return limit ? res : dp[pos][pre] = res;
}

int calc(int x) {
    //数位分离
    int pos = 0;
    while (x) a[pos++] = x % 10, x /= 10;        //把x按照进制分解到数组中
    return dfs(pos - 1, 0, true);
}

int main() {
    int l, r;
    //初始化
    memset(dp, -1, sizeof dp);
    while (cin >> l >> r)
        printf("%d\n", calc(r) - calc(l - 1));
    return 0;
}

二、DP解法

#include 

using namespace std;
const int N = 15;
int f[N][N];    //表示一共有i位，且最高位是j的数的个数

//预处理出不降数的数量数组f[N][N]
void init() {
    //1位数的方案数是1
    for (int i = 0; i <= 9; i++)f[1][i] = 1;
    //从2位数开始求
    for (int i = 2; i < N; i++)
        for (int j = 0; j <= 9; j++)    //最高位填的是j
            for (int k = j; k <= 9; k++)//次高位填的是k,需要比j大
                f[i][j] += f[i - 1][k]; //枚举次高位即可表示出f[i][j]
}

//计算[0~n]之间不降数的个数
int dp(int n) {
    //特判，如果是数字0，那么也是一种方案，因为也不降嘛
    if (!n) return 1;
    //拆出来每一位
    vector nums;
    while (n) nums.push_back(n % 10), n /= 10;
    int res = 0;
    int last = 0;//上一位数字是几，出发的时候从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];//答案加上一共i+1位，且最高位为j的数的个数
        //当前这位能不能填充x
        if (x < last) break;//如果降序，直接退出
        //更新last
        last = x;
        //特判处理一下末位,如果成功到达了这句话，就说明每一个数都是大于等于前一个数的
        if (!i)res++;
    }
    //返回结果
    return res;
}

int main() {
    //结果数组初始化，这次不是组合数就可以搞定了，而是还需要一个DP的过程
    init();
    int l, r;
    while (cin >> l >> r)
        cout << dp(r) - dp(l - 1) << endl;
    return 0;
}