最新华为OD机试真题-游乐园门票(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

游乐园门票(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🎀 游乐园门票

问题描述

A先生是一家著名游乐园"Wonderland"的经理,该游乐园提供4种不同的门票:一日票、三日票、周票和月票。每种门票的价格不同,持有门票的游客可以在有效期内无限次游玩。

具体而言:

• 一日票: 仅限当日有效
• 三日票: 从购买当日起,连续3天内有效
• 周票: 从购买当日起,连续7天内有效
• 月票: 从购买当日起,连续30天内有效

现在给定每种门票的价格,以及LYA计划在未来一年内的游玩日期,请帮助LYA计算出她需要支付的最低门票费用。

输入格式

第一行包含4个整数,分别表示一日票、三日票、周票和月票的价格。

第二行包含若干个整数,用空格分隔,表示LYA计划游玩的日期。日期按升序给出,范围在1到365之间。

输出格式

一个整数,表示LYA需要支付的最低门票费用。

样例输入

5 14 30 100
1 3 5 20 21 200 202 230

样例输出

40

样例解释

根据给定的门票价格和游玩日期,LYA最便宜的方式是每次购买一张一日票,共需支付8 * 5 = 40元。

数据范围

• 门票价格在1到10000之间
• 游玩日期数量在1到365之间

题解

我们可以使用动态规划来解决这个问题。定义 f[i] 为在第 i 天时,LYA需要支付的最低门票费用。初始时 f = 0。

对于每一天 i,我们有两种情况:

1. 如果LYA在第 i 天不需要游玩,那么 f[i] = f[i-1]。
2. 如果LYA在第 i 天需要游玩,那么我们需要考虑购买哪种门票最便宜。对于每种门票,我们计算从上次购买该门票到现在的最低费用,取最小值作为 f[i]。

最终的答案就是 f[365]。

参考代码

• Python

import sys

def mincostTickets(days, costs):
    dp = [sys.maxsize] * (days[-1] + 1)
    days_set = set(days)
    dp[0] = 0
    
    for i in range(1, days[-1] + 1):
        if i not in days_set:
            dp[i] = dp[i - 1]
        else:
            dp[i] = min(dp[i - 1] + costs[0], dp[max(0, i - 3)] + costs[1], dp[max(0, i - 7)] + costs[2], dp[max(0, i - 30)] + costs[3])
    
    return dp[-1]

costs = list(map(int, input().split()))
days = list(map(int, input().split()))
print(mincostTickets(days, costs))