【OD机试题解放笔记】Wonderland

题目描述

Wonderland是小王居住地一家很受欢迎的游乐园。
Wonderland目前有4种售票方式，分别为
一日票（1天）、
三日票（3天）、
周票（7天）
月票（30天）。
每种售票方式的价格由一个数组给出，每种票据在票面时限内可以无限制地进行游玩。例如：
小王在第10日买了一张三日票，小王可以在第10日、第11日和第12日进行无限制地游玩。
小王计划在接下来一年多次游玩该游乐园。小王计划地游玩日期将由一个数组给出。
现在，请您根据给出地售票价格数组和小王计划游玩日期数组，返回游玩计划所需要地最低消费。

输入描述
输入为2个数组：
售票价格数组为costs，costs.length = 4，默认顺序为一日票、三日票、周票和月票。
小王计划游玩日期数组为days，1 ≤ days.length ≤ 365，1 ≤ days[i] ≤ 365，默认顺序为升序。

输出描述
完成游玩计划的最低消费。

用例

思考

暴力解法思路：每个days[i] 都有四种买票选择(1/3/7/30)，令 n 为 days 长度，则共有 $4^n$种方案。这个过程中是可以优化的，比如相邻的游玩天数，如果一天买的票覆盖后续几天，那么后续几天可以不买票，但总的时间复杂度还是指数。仔细分析怎么优化每个游玩天数的购票方案，当天购票如果覆盖后续游玩的天数，那么后续就不用购票，后续购票时需要查询之前的购票记录，因此需要存储之前的购票方案。游玩天数是顺序递增的，不超过365天。定义数组 dp[i] 表示第 i 天游玩最低消费，i 下标从 0 开始，表示第一天。那么dp[j] (j > 0)最低消费为 $min(dp[max(0,j-1)]+5,dp[max(0,j-3)]+14,dp[max(0,j-7)]+30,dp[(max(0,j-30)+100])$。对于非游玩天数 j，dp[j] = dp[j-1]。用动态规划缓存子问题的解可避免暴力枚举大量的重复计算开销。

算法过程

1. 输入处理

   • 读取售票价格数组costs（一日票、三日票、周票、月票价格）
   • 读取计划游玩日期数组days（已按升序排列）

2. DP数组初始化

   • 创建长度为365的dp数组，dp[i]表示覆盖前i+1天（即第1天至第i+1天）的最低花费
   • 初始值均为0，代表初始状态无花费

3. 状态转移计算

   • 遍历全年365天（索引i从0到364，对应实际日期i+1）：
     • 若当天是游玩日（days数组包含i+1）：
       • 计算四种购票方案的花费：
         1. 买一日票：dp[i-1] + 一日票价格（覆盖当天）
         2. 买三日票：dp[i-3] + 三日票价格（覆盖当天及前2天）
         3. 买周票：dp[i-7] + 周票价格（覆盖当天及前6天）
         4. 买月票：dp[i-30] + 月票价格（覆盖当天及前29天）
       • 取四种方案的最小值作为dp[i]的值
     • 若当天不是游玩日：
       • 花费与前一天相同，即dp[i] = dp[i-1]（无需额外购票）

4. 结果输出

   • 最后一个游玩日对应的dp值即为最低总花费，通过dp[days[days.length-1]-1]获取

时间复杂度分析

• 遍历天数：循环执行365次，时间复杂度为O(365)
• 判断游玩日：每次循环中使用days.includes(i+1)，最坏情况下时间复杂度为O(n)（n为days数组长度）
• 总体复杂度：O(365×n)，由于n最大为365，可简化为O(1)（常数级复杂度，与输入规模无关）

空间复杂度分析

• DP数组：使用长度为365的数组，空间复杂度为O(365)
• 其他变量：输入数组costs（固定长度4）和days（最大长度365），空间复杂度为O(n)
• 总体复杂度：O(1)（常数级空间，与输入规模无关）

算法特点

• 利用动态规划思想，通过每天的最优子结构推导出全局最优解
• 直接遍历全年天数，无需复杂的日期映射逻辑
• 对非游玩日进行状态继承，减少无效计算
• 适用于所有可能的游玩计划（1≤days.length≤365），且时间和空间消耗稳定

代码

function solution() {
  const costs = readline().split(' ').map(Number);
  const days = readline().split(" ").map(Number);

  const dp = Array(365).fill(0);
  for (let i = 0; i < 365; i++) {
    if (days.includes(i+1)) {
      dp[i] = Math.min(dp[Math.max(0, i-1)] + costs[0],
                       dp[Math.max(0, i-3)] + costs[1],
                       dp[Math.max(0, i-7)] + costs[2],
                       dp[Math.max(0, i-30)] + costs[3]);
    } else {
      dp[i] = dp[Math.max(0, i-1)];
    }
  }
   
  console.log(dp[days[days.length-1]]);
}

const cases = [
  `5 14 30 100
  1 3 5 20 21 200 202 230`,
];

let caseIndex = 0;
let lineIndex = 0;

const readline = (function () {
  let lines = [];
  return function () {
    if (lineIndex === 0) {
      lines = cases[caseIndex]
        .trim()
        .split("\n")
        .map((line) => line.trim());
    }
    return lines[lineIndex++];
  };
})();

cases.forEach((_, i) => {
  caseIndex = i;
  lineIndex = 0;
  solution();
});