AcWing 1083. Windy数 数位DP模板题
原题链接
中等
作者:
皓首不倦
,
2020-07-28 01:10:47
,
所有人可见
,
阅读 588
# 小于等于n的合法的数值个数
def get_num(n):
if n == 0:
return 0
arr = []
val = n
while val:
arr.append(val % 10)
val //= 10
# 前i位做选择,合法的数值个数
# 约束条件:更高的一位选择数值是higher_val
# 所有更高位全部选择最大值的标记是all_higher_max
# 所有更高位全部选择是0标记是all_higher_zero
from functools import lru_cache
@lru_cache(typed=False, maxsize=128000000)
def dp(i, higher_val, all_higher_max, all_higher_zero):
if i == 0:
upper_bound = arr[i] if all_higher_max else 9
lower_bound = 1 if all_higher_zero else 0
if all_higher_zero:
return max(0, upper_bound - lower_bound + 1)
else:
cnt = 0
for cur_val in range(lower_bound, upper_bound + 1):
if abs(cur_val - higher_val) >= 2:
cnt += 1
return cnt
else:
upper_bound = arr[i] if all_higher_max else 9
lower_bound = 0
if all_higher_zero:
ans = 0
for cur_val in range(lower_bound, upper_bound + 1):
ans += dp(i-1, cur_val, all_higher_max and cur_val == arr[i], all_higher_zero and cur_val == 0)
return ans
else:
ans = 0
for cur_val in range(lower_bound, upper_bound+1):
if abs(cur_val - higher_val) >= 2:
ans += dp(i-1, cur_val, all_higher_max and cur_val == arr[i], all_higher_zero and cur_val == 0)
return ans
return dp( len(arr)-1, 0, True, True )
while True:
try:
a, b = map(int, input().split())
except:
break
print( get_num(b) - get_num(a-1) )