当前位置: 代码迷 >> 综合 >> AcWing 数位DP相关问题 1082. 数字游戏
  详细解决方案

AcWing 数位DP相关问题 1082. 数字游戏

热度:21   发布时间:2024-02-05 15:13:12.0
import sys
from functools import lru_cache
sys.stdin = open('data.txt', 'r')# 小于等于n的符合条件的数字个数
def get_num(n):if n == 0:return 1arr = []val = nwhile val:arr.append(val % 10)val //= 10# 前i位做选择,更高的一位选择数值是higher_val且更高的所有位都选择了最大值的标志是all_higher_max的约束下,合法的数值的个数@lru_cache(typed=False, maxsize=128000000)def dp(i, higher_val, all_higer_max):if i == 0:low_bound, up_bound = higher_val, arr[i] if all_higer_max else 9return max(0, up_bound - low_bound + 1)else:low_bound, up_bound = higher_val, arr[i] if all_higer_max else 9if low_bound > up_bound:return 0ans = 0for cur_val in range(low_bound, up_bound+1):ans += dp(i-1, cur_val, all_higer_max and cur_val == arr[i])return ansreturn dp(len(arr)-1, 0, True)while True:try:a, b = map(int, input().split())except:breakprint( get_num(b) - get_num(a-1) )