1 条题解

  • 0
    @ 2023-1-10 18:01:01
    #include <bits/stdc++.h>
    using namespace std;
    int L, R;
    int dp[15][10];  // 记忆化搜索 dp[pos][pre]
    int d[15], dlen; // d[dlen]~d[1]
    // 做到了第 pos 位,前一位是 pre,是否顶到了上限
    int dfs(int pos, int pre, bool limit)
    {
        if (pos == 0)
            return 1;
        // 算过了没贴边的结果的话就直接返回
        if (!limit && dp[pos][pre] != -1)
            return dp[pos][pre];
        // 当前这一位的上限
        int up = limit ? d[pos] : 9;
        int sum = 0;                          // 记录方案数
        for (int now = pre; now <= up; now++) // 枚举当前这一位
            sum += dfs(pos - 1, now, limit && now == d[pos]);
        // 如果前面没贴边,就记忆化一下
        if (!limit)
            dp[pos][pre] = sum;
        return sum;
    }
    // 计算 0~x 不含有不吉利成分的数的数量
    int cal(int x)
    {
        if (x == 0)
            return 1;
        dlen = 0;
        for (int i = x; i != 0; i /= 10)
            d[++dlen] = i % 10;
        return dfs(dlen, 0, true);
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        while (cin >> L >> R)
        {
            memset(dp, -1, sizeof(dp));
            cout << cal(R) - cal(L - 1) << "\n";
        }
        return 0;
    }
    
    
    • 1

    「一本通 5.3 例 2」数字游戏(不降数)

    信息

    ID
    816
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    58
    已通过
    27
    上传者