返回目录

题目描述

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，默认顺序为升序。

输出描述

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

示例：

解题思路

我们可以使用动态规划。核心思想是为每个游玩日期计算最低消费成本，并存储这些结果以供后续日期使用。具体步骤如下：

1. 创建一个数组 dp 以存储直至每一天的最低消费。数组的长度为365天加1（因为数组是从0开始的，而天数是从1开始的）。
2. 初始化 dp[0] = 0，因为在开始之前没有任何消费。

3. 遍历每一天，对于每一天，我们有几种选择：

   • 如果这一天不在计划游玩日期中，则这一天的消费与前一天相同，即 dp[i] = dp[i-1]。

   • 如果这一天在计划游玩日期中，我们需要考虑三种票价中的最低消费：

     • 一日票的消费是：dp[i-1] + costs[0]。
     • 三日票的消费是：dp[max(i-3, 0)] + costs[1]。
     • 周票的消费是：dp[max(i-7, 0)] + costs[2]。
     • 月票的消费是：dp[max(i-30, 0)] + costs[3]。
   • 对于这一天，选择上述四种情况中的最小值作为 dp[i] 的值。
4. 最终 dp[365] 即为所求的最低消费。

Python算法源码

def mincostTickets(costs, days):
    maxDay = max(days)
    travelDays = [False] * (maxDay + 1)
    for day in days:
        travelDays[day] = True

    dp = [0] * (maxDay + 1)
    for i in range(1, maxDay + 1):
        if not travelDays[i]:
            dp[i] = dp[i - 1]
            continue

        cost1 = dp[max(0, i - 1)] + costs[0]
        cost3 = dp[max(0, i - 3)] + costs[1]
        cost7 = dp[max(0, i - 7)] + costs[2]
        cost30 = dp[max(0, i - 30)] + costs[3]

        dp[i] = min(cost1, cost3, cost7, cost30)

    return dp[maxDay]

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

# 调用mincostTickets方法计算最低消费，并打印结果
print(mincostTickets(costs, days))

C语言算法源码

#include <stdio.h>
#include <stdlib.h>

// 找到两个整数的最小值的函数
int min(int a, int b) {
    return (a < b) ? a : b;
}

// 找到车票最小花费的函数
int getMin(int a, int b, int c, int d) {
    int min1 = (a < b) ? a : b;
    int min2 = (c < d) ? c : d;
    return (min1 < min2) ? min1 : min2;
}

// 获取结果的函数
int getResult(int* costs, int costsSize, int* days, int daysSize) {
    // 最大旅行天数
    int maxDay = days[daysSize - 1];

    // dp[i] 表示完成前 i 天的所有旅行日所需的最小花费
    int* dp = (int*)calloc(maxDay + 1, sizeof(int)); // dp[0] 默认为0，表示前0天的花费为0

    // 索引指向当前需要完成的旅行日，从第一天开始
    int index = 0;

    // 从第1天遍历到最大天数
    for (int i = 1; i <= maxDay; ++i) {
        if (i == days[index]) {
            // 如果第i天是旅行日，则有四个花费选项

            // 选项1：购买“一天票”，仅用于第i天的旅行。因此，前i天的花费为 dp[i-1] + costs[0]
            int buy1 = dp[i - 1] + costs[0];

            // 选项2：购买“三天票”，可以用于第i天、i-1天和i-2天（相当于在第i-2天购买）。因此，前i天的花费为 dp[i-3] + costs[1]
            int buy3 = (i >= 3 ? dp[i - 3] : 0) + costs[1];

            // 选项3：购买“七天票”，可以用于第i~i-6天（相当于在第i-6天购买）。因此，前i天的花费为 dp[i-7] + costs[2]
            int buy7 = (i >= 7 ? dp[i - 7] : 0) + costs[2];

            // 选项4：购买“三十天票”，可以用于第i~i-29天（相当于在第i-29天购买）。因此，前i天的花费为 dp[i-30] + costs[3]
            int buy30 = (i >= 30 ? dp[i - 30] : 0) + costs[3];

            // 选择四个选项中的最小花费作为 dp[i]
            dp[i] = getMin(buy1, buy3, buy7, buy30);

            // 移动到下一个旅行日（days按升序排列，所以索引和days[index]正相关）
            index++;
        } else {
            // 如果第i天不是旅行日，则第i天不需要任何费用，即前i天的费用与前i-1天的费用相同
            dp[i] = dp[i - 1];
        }
    }

    return dp[maxDay];
}

int main() {
    int costs[4];
    int days[365]; // 假设一年中最多的天数
    int costsSize = 4;
    int daysSize = 0;

    // 从用户输入获取车票费用
    scanf("%d %d %d %d", &costs[0], &costs[1], &costs[2], &costs[3]);

    // 从用户输入获取旅行日
    int day;
    while (scanf("%d", &day) == 1) {
        days[daysSize++] = day;
    }

    // 调用getResult函数计算最小费用并打印结果
    printf("%d\n", getResult(costs, costsSize, days, daysSize));

    return 0;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建一个Scanner对象以获取用户输入
        Scanner scanner = new Scanner(System.in);

        // 从用户输入中获取车票费用，格式为用空格分隔的四个整数
        int[] costs = Arrays.stream(scanner.nextLine().split(" "))
                            .mapToInt(Integer::parseInt)
                            .toArray();

        // 从用户输入中获取旅行天数，格式为用空格分隔的整数
        int[] days = Arrays.stream(scanner.nextLine().split(" "))
                           .mapToInt(Integer::parseInt)
                           .toArray();

        // 关闭Scanner对象
        scanner.close();

        // 调用mincostTickets方法计算最小费用并打印结果
        System.out.println(mincostTickets(costs, days));
    }

    public static int mincostTickets(int[] costs, int[] days) {
        // 找到days数组中的最大值以确定旅行的最后一天
        int maxDay = Arrays.stream(days).max().getAsInt();

        // 创建长度为maxDay+1的布尔数组，标记每一天是否需要旅行
        boolean[] travelDays = new boolean[maxDay + 1];
        for (int day : days) {
            travelDays[day] = true;
        }

        // 创建长度为maxDay+1的整数数组，保存每一天的最小费用
        int[] dp = new int[maxDay + 1];
        for (int i = 1; i <= maxDay; i++) {
            // 如果这一天不需要旅行，则其最小费用与前一天相同
            if (!travelDays[i]) {
                dp[i] = dp[i - 1];
                continue;
            }

            // 计算购买1、3、7和30天车票的费用
            int cost1 = dp[Math.max(0, i - 1)] + costs[0];
            int cost3 = dp[Math.max(0, i - 3)] + costs[1];
            int cost7 = dp[Math.max(0, i - 7)] + costs[2];
            int cost30 = dp[Math.max(0, i - 30)] + costs[3];

            // 这一天的最小费用是上述计算的费用的最小值
            dp[i] = Math.min(Math.min(cost1, cost3), Math.min(cost7, cost30));
        }

        // 返回最后一天的最小费用，即整个旅行计划的最小费用
        return dp[maxDay];
    }
}