1 条题解

  • 0
    @ 2023-1-10 18:11:04
    #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,是否顶到了上限,之前是否都填的 0
    int dfs(int pos, int pre, bool limit, bool zero)
    {
        if (pos == 0)
            return 1;
        // 算过了没贴边的结果的话就直接返回
        if (!limit && !zero && dp[pos][pre] != -1)
            return dp[pos][pre];
        // 当前这一位的上限
        int up = limit ? d[pos] : 9;
        int sum = 0;                        // 记录方案数
        for (int now = 0; now <= up; now++) // 枚举当前这一位
        {
            if (zero) // 当前是第一个数,前面都是前导 0
            {
                // 第一个数没有差至少为2的限制
                sum += dfs(pos - 1, now, limit && now == d[pos], zero && now == 0);
            }
            else
            {
                if (abs(now - pre) < 2)
                    continue;
                sum += dfs(pos - 1, now, limit && now == d[pos], zero && now == 0);
            }
        }
        // 如果前面没贴边,就记忆化一下
        if (!limit && !zero)
            dp[pos][pre] = sum;
        return sum;
    }
    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, true);
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> L >> R;
        memset(dp, -1, sizeof(dp));
        cout << cal(R) - cal(L - 1) << "\n";
        return 0;
    }
    
    
    • 1

    信息

    ID
    817
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    56
    已通过
    23
    上传者