OD C卷 - Wonderland游乐园

Wonderland游乐园（200）

• 游乐园有四种售票方式，分别为一日票，三日票，周票（7天）、月票（30天）；
• 每种票据在时限内可以无限制游玩，如第10天买了一个三日票，则可以在第10/11/12日进行无限制游玩；
• 根据售票价格数组、游玩日期数组，计算最低消费；

输入描述：
第一行输入售票价格数组costs; 顺序为一日、三日、周票、月票
第二行输入游玩日期（一年中第几天）数组days；数组长度为【1,365】，日期值也在【1,365】，升序排序；
输出描述：
游玩的最低消费

示例1
输入：
5 14 30 100
1 3 5 20 21 200 202 230
输出：
40

思路：

• 动态规划
• 对于每个游玩的日期，前一天买一日票，前三天买三日票，前一个星期买周票，前一个月买月票，所有方案中取最小成本；
• i 遍历1-365 的所有日期
• j 表示days数组的索引

costs = list(map(int, input().strip().split()))
days = list(map(int, input().strip().split()))# 假设成本无穷大
dp = [float('inf') for _ in range(370)]
dp[0] = 0j = 0 # 游玩日期数组索引 第
for i in range(1, 366): # i 第1-365之间的值if j < len(days) and i == days[j]:dp[i] = min(dp[i], dp[max(0, i - 1)] + costs[0])dp[i] = min(dp[i], dp[max(0, i - 3)] + costs[1])dp[i] = min(dp[i], dp[max(0, i - 7)] + costs[2])dp[i] = min(dp[i], dp[max(0, i - 30)] + costs[3])j += 1else:dp[i] = dp[i - 1]print(dp)
print(dp[365]) # 第365天