AcWing 1085. 不要62 简单数位DP
原题链接
中等
作者:
皓首不倦
,
2020-07-28 02:48:47
,
所有人可见
,
阅读 546
def get_num(n):
if n <= 0:
return 1 # 统一把1算进答案里面,相减就抵消掉了
arr = []
val = n
while val:
arr.append(val % 10)
val //= 10
from functools import lru_cache
@lru_cache(typed=False, maxsize=999000000)
def dp(i, higher_val, all_higher_max):
upper_bound = arr[i] if all_higher_max else 9
cnt = 0
for cur_val in range(upper_bound+1):
if cur_val == 4:
continue
if higher_val == 6 and cur_val == 2:
continue
cnt += 1 if i == 0 else dp(i-1, cur_val, all_higher_max and cur_val == arr[i])
return cnt
return dp(len(arr)-1, 0, True)
while True:
a, b = map(int, input().split())
if a == 0 and b == 0:
break
print( get_num(b) - get_num(a-1) )