刷题笔记合集🔗

题目描述

Wonderland是一家游乐园，提供4种售票方式:

• 一日票(1天)
• 三日票(3天)
• 周票(7天)
• 月票(30天)

每种票在有效期内可以无限制游玩。例如:

第10日买三日票，可以在第10、11、12日无限制游玩

现给定:

1. 售票价格数组costs
2. 计划游玩日期数组days

求完成游玩计划的最低消费。

输入格式

第一行: 4个整数，表示售票价格数组costs

• 依次为一日票、三日票、周票、月票价格

第二行: n个整数，表示计划游玩日期数组days

• 1 ≤ n ≤ 365
• 1 ≤ days[i] ≤ 365
• 升序排列

输出格式

一个整数，表示最低消费金额

约束说明

• costs.length = 4
• 1 ≤ days.length ≤ 365
• 1 ≤ days[i] ≤ 365
• days升序排列

样例输入1

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

样例输出1

40

样例说明1

根据价格和游玩日期分析:

• 每次买一日票最省钱
• 需要买8张一日票
• 每张5元，总共40元

题目解析

本题是一个动态规划问题，关键点在于:

1. 状态定义

   • dp[i]表示前i天完成游玩的最小花费
   • dp[0] = 0，表示前0天花费为0

2. 状态转移

   • 非游玩日: dp[i] = dp[i-1]
   • 游玩日: dp[i] = min(四种购票方案)
     • 一日票: dp[i-1] + costs[0]
     • 三日票: dp[i-3] + costs[1]
     • 周票: dp[i-7] + costs[2]
     • 月票: dp[i-30] + costs[3]

3. 边界处理

   • i < 3时，dp[i-3]取0
   • i < 7时，dp[i-7]取0
   • i < 30时，dp[i-30]取0

4. 结果获取

   • 返回dp[maxDay]，其中maxDay是最大游玩日

时间复杂度: O(maxDay)，其中maxDay是最大游玩日

参考代码

def solve():
    # 读取输入
    costs = list(map(int, input().split()))
    days = list(map(int, input().split()))
    
    # 最大游玩日
    max_day = days[-1]
    
    # dp[i]表示前i天完成游玩的最小花费
    dp = [0] * (max_day + 1)
    
    # 当前处理的游玩日索引
    idx = 0
    
    # 遍历每一天
    for i in range(1, max_day + 1):
        if i == days[idx]:
            # 游玩日，考虑四种购票方案
            buy1 = dp[i-1] + costs[0]  # 一日票
            buy3 = (dp[i-3] if i >= 3 else 0) + costs[1]  # 三日票
            buy7 = (dp[i-7] if i >= 7 else 0) + costs[2]  # 周票
            buy30 = (dp[i-30] if i >= 30 else 0) + costs[3]  # 月票
            
            dp[i] = min(buy1, buy3, buy7, buy30)
            idx += 1
        else:
            # 非游玩日
            dp[i] = dp[i-1]
            
    return dp[max_day]

if __name__ == "__main__":
    print(solve())

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int solve(vector<int>& costs, vector<int>& days) {
        // 最大游玩日
        int max_day = days.back();