刷题笔记合集🔗

Wonderland

问题描述

Wonderland 是小柯居住地一家很受欢迎的游乐园。Wonderland 目前有 种售票方式，分别为一日票（ 天）、三日票（ 天）、周票（ 天）和月票（ 天）。

每种售票方式的价格由一个数组给出，每种票据在票面时限内可以无限制地进行游玩。例如：

小柯在第 日买了一张三日票，小柯可以在第 日、第 日和第 日进行无限制地游玩。

小柯计划在接下来一年多次游玩该游乐园。小柯计划地游玩日期将由一个数组给出。

现在，请您根据给出地售票价格数组和小柯计划游玩日期数组，返回游玩计划所需要地最低消费。

输入格式

输入为 个数组：

第一行是售票价格数组 ，，默认顺序为一日票、三日票、周票和月票。

第二行是小柯计划游玩日期数组 ，，，默认顺序为升序。

输出格式

输出一个整数，表示完成游玩计划的最低消费。

样例输入

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

样例输出

40

数据范围

题解

这道题目本质上是一个动态规划问题，需要找出最优的购票方案来覆盖所有计划游玩的日期，并使总花费最小。

首先分析一下题目：小柯计划在一年中的某些特定日期去游乐园，游乐园提供四种不同有效期的票（1天、3天、7天和30天），每种票有不同的价格。问题是如何选择购票方式使总费用最低。

解题思路是使用动态规划。定义 dp[i] 表示前 i 天内，完成所有游玩日所需的最小花费。关键在于如何推导状态转移方程。

对于每一天，有两种情况：

1. 如果第 i 天不是计划游玩的日期，那么 dp[i] = dp[i-1]，即不需要额外花费
2. 如果第 i 天是计划游玩的日期，那么需要选择买哪种票最划算

当第 i 天是游玩日时，有四种购票选择：

• 买一日票：dp[i] = dp[i-1] + costs[0]
• 买三日票：dp[i] = dp[i-3] + costs[1]（如果 i < 3，则用 0 代替 dp[i-3]）
• 买七日票：dp[i] = dp[i-7] + costs[2]（如果 i < 7，则用 0 代替 dp[i-7]）
• 买月票：dp[i] = dp[i-30] + costs[3]（如果 i < 30，则用 0 代替 dp[i-30]）

最终取这四种选择中的最小值作为 dp[i]。

来看一个具体例子：假设一日票5元，三日票14元，周票30元，月票100元，游玩日期是第1、3、5天。

• 第1天：可以买一日票（dp[1]=5），三日票（dp[1]=14），周票（dp[1]=30）或月票（dp[1]=100），最小值是5
• 第2天：不是游玩日，dp[2]=dp[1]=5
• 第3天：可以买一日票（dp[3]=dp[2]+5=10），也可以买三日票覆盖第1天和第3天（dp[3]=14），买周票或月票更贵，所以dp[3]=10
• 第4天：不是游玩日，dp[4]=dp[3]=10
• 第5天：可以买一日票（dp[5]=dp[4]+5=15），三日票（dp[5]=dp[2]+14=19），周票或月票更贵，所以dp[5]=15

最终答案是dp[5]=15元。

时间复杂度是O(n)，其中n是最大游玩日。空间复杂度也是O(n)。这对于题目给定的数据范围（最大游玩日不超过365）是完全可接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
costs = list(map(int, input().split()))
days = list(map(int, input().split()))

# 计算最小花费的函数
def calc_min_cost():
    # 最大游玩日
    max_d = days[-1]
    
    # dp[i]表示前i天完成所有游玩所需的最小花费
    dp = [0] * (max_d + 1)
    
    # 用于指向当前处理的游玩日
    idx = 0
    
    # 遍历每一天计算最小花费
    for i in range(1, max_d + 1):
        if i == days[idx]:
            # 四种购票选择
            day1 = dp[i - 1] + costs[0]
            day3 = (dp[i - 3] if i >= 3 else 0) + costs[1]