AcWing 1082. 数字游戏 简单数位DP
原题链接
中等
作者:
皓首不倦
,
2020-07-27 23:23:06
,
所有人可见
,
阅读 525
import sys
sys.stdin = open('data.txt', 'r')
# 小于等于n的符合条件的数字个数
def get_num(n):
if n == 0:
return 1
arr = []
val = n
while val:
arr.append(val % 10)
val //= 10
# 前i位做选择,更高的一位选择数值是higher_val且更高的所有位都选择了最大值的标志是all_higher_max的约束下,合法的数值的个数
def dp(i, higher_val, all_higer_max):
if i == 0:
low_bound, up_bound = higher_val, arr[i] if all_higer_max else 9
return max(0, up_bound - low_bound + 1)
else:
low_bound, up_bound = higher_val, arr[i] if all_higer_max else 9
if low_bound > up_bound:
return 0
ans = 0
for cur_val in range(low_bound, up_bound+1):
ans += dp(i-1, cur_val, all_higer_max and cur_val == arr[i])
return ans
return dp(len(arr)-1, 0, True)
while True:
try:
a, b = map(int, input().split())
except:
break
print( get_num(b) - get_num(a-1) )