Wonderland - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

Wonderland 是小王居住地一家很受欢迎的游乐园。Wonderland目前有 4 种售票方式,分别为一日票(天)、三日票(3 天)，周票( 7 天)和月票( 30 天) 。

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

例如:小王在第10日买了一张三日票，小王可以在第10日、第11日和第12日进行无限制地游玩，小王计划在接下来玩计划所需要地最低消费。

小王一年多次游玩该游乐园。小王计划地游玩日期将由一个数组给出。

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

输入描述

第一行为售票价格数组 costs ;

第二行为小王计划游玩日期数组；

costs.length = 4，默认顺序为一日票、三日票、周票和月票。

1 <= days.length <= 365，1 <= days[i]<= 365 ，默认顺序为升序。

输出描述

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

示例1

输入：
5 14 30 100
1 3 5 20 21 200 202 230

输出：
40

说明：
根据售票价格数组和游玩日期数组给出的信息，发现每次去玩的时候买一张一日票是最省钱的，所以小王会买 8 张一日票，每张 5 元，最低花费是 40 元。

题解

本题是一道典型的动态规划问题。

首先，我们可以创建一个长度为366 + 30 的数组dp，dp[x] 表示从计划游玩从第x到第365天的最低消费。

然后，从后往前遍历日期，根据游玩计划和售票价格数组进行动态规划转移。具体转移方程如下：

如果当前日期在计划游玩的日期中，那么可以选择购买一日票、三日票、周票或月票，分别更新dp[x]的值。
如果当前日期不在计划游玩的日期中，那么dp[x]等于dp[x+1]，表示不购买任何票。

最终，dp[1]即为从第1天到第365天的最低消费。

Java

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

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 售票价格数组
        int[] costs = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        boolean[] days = new boolean[366];
        Arrays.fill(days, false);

        // 标记计划游玩的日期
        Arrays.stream(scanner.nextLine().split(" "))
                .map(Integer::parseInt)
                .forEach(d -> days[d] = true);

        // dp[x] 表示从计划游玩 [x: 365] 日期最低消费
        // 为了方便动态规划转移，将数组扩展 30 个长度
        int[] dp = new int[366 + 30];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int d = 366; d < dp.length; d++) dp[d] = 0;

        for (int x = 365; x > 0; x--) {
            if (days[x]) {  // 日期 x 计划游玩
                dp[x] = Math.min(dp[x], dp[x + 1] + costs[0]);  // 购买一日票
                dp[x] = Math.min(dp[x], dp[x + 3] + costs[1]);  // 购买三日票
                dp[x] = Math.min(dp[x], dp[x + 7] + costs[2]);  // 购买周票
                dp[x] = Math.min(dp[x], dp[x + 30] + costs[3]);  // 购买月票
            } else {
                dp[x] = dp[x + 1];
            }
        }

        System.out.println(dp[1]);
    }
}

Python

from cmath import inf

# 售票价格数组
costs = list(map(int, input().split()))

days = [False] * 366
for d in list(map(int, input().split())):
    days[d] = True

# dp[x] 表示从 计划游玩 [x: 365] 日期最低消费
# 为了方便动态规划转移，将数组扩展 30 个长度
dp = [inf] * 366 + [0] * 30
for x in range(365, 0, -1):
    if days[x]:  # 日期 x 计划游玩
        dp[x] = min(dp[x], dp[x + 1] + costs[0])  # 购买一日票
        dp[x] = min(dp[x], dp[x + 3] + costs[1])  # 购买三日票
        dp[x] = min(dp[x], dp[x + 7] + costs[2])  # 购买周票
        dp[x] = min(dp[x], dp[x + 30] + costs[3])  # 购买月票
    else:
        dp[x] = dp[x + 1]

print(dp[1])

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

template <typename T>
vector<T> readList() {
    string input;
    getline(cin, input);
    stringstream stream(input);
    vector<T> result;
    T value;
    while (stream >> value) {
        result.push_back(value);
    }
    return result;
}

int main() {
    // 售票价格数组
    vector<int> costs = readList<int>();

    // 标记计划游玩的日期
    vector<bool> days(366, false);
    int day;
    while (cin >> day) {
        days[day] = true;
    }

    // dp[x] 表示从计划游玩 [x: 365] 日期最低消费
    // 为了方便动态规划转移，将数组扩展 30 个长度
    vector<int> dp(366 + 30, INT_MAX);
    fill(dp.begin() + 366, dp.end(), 0);

    for (int x = 365; x > 0; x--) {
        if (days[x]) {  // 日期 x 计划游玩
            dp[x] = min(dp[x], dp[x + 1] + costs[0]);  // 购买一日票
            dp[x] = min(dp[x], dp[x + 3] + costs[1]);  // 购买三日票
            dp[x] = min(dp[x], dp[x + 7] + costs[2]);  // 购买周票
            dp[x] = min(dp[x], dp[x + 30] + costs[3]);  // 购买月票
        } else {
            dp[x] = dp[x + 1];
        }
    }

    cout << dp[1] << endl;

    return 0;
}