题解 | #神秘餐馆#

神秘餐馆

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

写了个python的dfs,一个树节点有m个子节点,但是准确率只有46%,求改正


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
门头沟学院 Java
变异者:10元一天好笑程度100% 我去是哪个意思好笑程度1000%
点赞 评论 收藏
分享
牛牛不会牛泪:可以先别急着租房,去青旅,或者订个近点的宾馆待几天。先看看要做的能不能学到东西,然后看文档完不完善,写的好不好,mentor对你咋样,公司氛围啥的。情况不对赶快跑路找下家
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务