1085 不要62(数位dp)

1. 问题描述:

2. 思路分析:

3. 代码如下:

from typing import List


class Solution:
    # f[i][j]表示总共有i位最高位为j的方案数目
    def init(self, N: int, f: List[List[int]]):
        # 只有一位数字的方案
        for i in range(10):
            # 主要是不是4说明就是满足要求
            if i != 4:
                f[1][i] = 1
        for i in range(2, N):
            # 枚举总共有i位数字最高位填j
            for j in range(10):
                # 最高位为4的那么直接跳过
                if j == 4: continue
                # 枚举次高位填k
                for k in range(10):
                    # 筛选掉不满足方案次高位为4或者是上一位与当前这一位构成了62说明不满足条件跳过
                    if j == 4 or (j == 6 and k == 2): continue
                    # 方案合法累加到结果即可
                    f[i][j] += f[i - 1][k]

    # 求解区间[0, n]中满足题目要求的方案数目
    def dp(self, n: int, f: List[List[int]]):
        # 特判一下n = 0的情况
        if n == 0: return 1
        nums = list()
        while n > 0:
            nums.append(n % 10)
            n //= 10
        # last记录前缀信息, 因为下一位只与上一位是有关系的所以使用last记录上一位数字是什么
        res, last = 0, 0
        for i in range(len(nums) - 1, -1, -1):
            x = nums[i]
            # 枚举最高位填0~x-1的情况
            for k in range(x):
                # 当前这一位是4或者与上一位构成了62那么直接跳过
                if k == 4 or (last == 6 and k == 2): continue
                res += f[i + 1][k]
            # 判断这一位是否是4或者构成了62如果是说明进入循环的下一位的时候右边的分支是不合法的
            if x == 4 or (last == 6 and x == 2):
                break
            else:
                # 更新当前的last进入循环的下一位的时候表示上一位数字
                last = x
            # 最右边的那个分支
            if i == 0: res += 1
        return res

    def process(self):
        # 预处理列表f
        N = 11
        f = [[0] * 10 for i in range(N)]
        while True:
            n, m = map(int, input().split())
            if n == 0 and m == 0: break
            self.init(N, f)
            print(self.dp(m, f) - self.dp(n - 1, f))


if __name__ == "__main__":
    Solution().process()
上一篇:ARC127C Binary Strings 思维 二进制 树


下一篇:如何关闭SpringSecurity的权限认证