题解

1 条题解

  • 1
    @ 2022-08-14 12:12:08
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    long long int n, m;
    int a[20], dp[20][10]; //a用来存放数字的每位数
    int dfs(int pos, int pre, bool
            limit) { //pre表示pos位数的下一位数的值,例如pos=3表示当前位为百位,则pre表示十位数的值
        if (pos == 0)
            return 1;
    
        if (!limit && dp[pos][pre] != -1)
            return dp[pos][pre];
    
        int ans = 0;
        int up = limit ? a[pos] : 9;
    
        for (int i = 0; i <= up; i++) {
            if (i < pre)
                continue;
    
            ans += dfs(pos - 1, i, i == a[pos] &&
                       limit); //从数字的高位向低位递归,新limit的取值根据原limit和i的取值决定,例如246,当pos表示十位数时,如果原limit=1(百位数=2)并且十位数等于4,那么下一次的搜索就会有限制(个位数上界限制为6)
        }
    
        // if(!limit)
        dp[pos][pre] = ans;
        return ans;
    }
    
    int solve(int x) {
        int pos = 0; //pos用于记录当前位数
    
        while (x) {
            a[++pos] = x % 10; //pos从1开始表示位数从个位到高位
            x /= 10; //如246在数组中的存放方式是6 4 2
        }
    
        return dfs(pos, 0, 1); //从数字的最高位开始
    }
    
    int main() {
        while (cin >> n >> m) {
            memset(dp, -1, sizeof(dp));
            cout << solve(m) - solve(n - 1) << endl; //减的是n-1不是n,n自身要算进去
        }
    
        return 0;
    }
    
  • 1

信息

ID
1518
难度
9
分类
动态规划 | 搜索 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者