AcWing 1085. 不要62 python
原题链接
中等
作者:
ppz
,
2021-01-11 19:48:52
,
所有人可见
,
阅读 344
python代码
N = 10 # 数据位数
# 状态数组:f[i, j] 表示i位数,最高位是j的满足要求的数的个数
f = [[0] * 10 for _ in range(N)]
def init():
global N
# 一位时
for i in range(10):
if i != 4:
f[1][i] = 1
# DP 推f
for i in range(2, N):
for j in range(10):
if j == 4: continue
for k in range(10):
if k == 4 or (j == 6 and k == 2): continue
f[i][j] += f[i-1][k]
# 动规求树形
def dp(n):
# 边界判断
if n == 0:
return 1
# 拆分数字,从低位到高位
nums = []
while n:
nums.append(n % 10)
n //= 10
res = 0 # 答案
last = 0 # 本题中记录的是前一个数
# 从高位到低位枚举每一位
for i in range(len(nums)-1, -1, -1):
x = nums[i]
for j in range(x): # 枚举左分支0~x-1
if j == 4 or ( last == 6 and j == 2): continue
res += f[i+1][j]
if x == 4 or (last == 6 and x == 2): break
last = x
if i == 0: res += 1
return res
# 初始化
init()
# 读入数据
while True:
try:
line = input()
except:
break
a, b = list(map(int, line.split()))
if a == 0 and b == 0: break
print(dp(b) - dp(a-1))