# 题解 | #神秘餐馆#

https://ac.nowcoder.com/acm/problem/21312

prices = []
for _ in range(n):
line = input().strip()  # 使用 strip() 移除字符串两端的空白字符
prices.append(line)

price_int = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
char = prices[i][j]
if char.isdigit():
price_int[i][j] = int(char)
elif char.isalpha():
if char.isupper():
price_int[i][j] = ord(char) - ord('A') + 10
else:
price_int[i][j] = ord(char) - ord('a') + 36

# 递归树有m个分支，每个分支递归完，返回下一层级的最大值，再和本层级的其它分支比大小
def dfs(day, budget_left, memory):
if budget_left < 0 or day >= n:
return day
max_day = day            #m个个分支的最大值
for i in range(m):
if budget_left >= price_int[day][i]:
next_day = day + 1
next_budget = budget_left
if day>=7 and next_day != 0:
next_budget -= price_int[day][memory[day - 7]]
else:
next_budget -= price_int[day][i]
memory.append(i)
current_day = dfs(next_day, next_budget, memory)
max_day = max(max_day, current_day)
memory.pop()         # 回溯，防止其它分支的输入被篡改
return max_day

memory = []
max_days = dfs(0, budget, memory)
print(max_days)

05-21 15:03