思路：动态规划

我们可以定义$f[i]$为前$i$天游玩的最小花费，首先我们需要将所有的$i(0\le i\le 365)$为正无穷，然后初始化$f[0]=0$

对于第$i$天，有两种情况

• 情况1：第$i$天不位于计划游玩日期数组中，那么很显然有状态转移方程$f[i]=f[i-1]$
• 情况2：第$i$天位于计划游玩日期数组中，由于我们有四种买票方式，因此就可以分四种情况讨论

情况2.1：在第$i$天当天购买一日票，对应的开销为$f[i-1]+costs[0]$

情况2.2：在第$i$天前三天购买三日票，对应的开销为$f[i-3]+costs[1]$

情况2.3：在第$i$天前七天购买一日票，对应的开销为$f[i-7]+costs[2]$

情况2.4：在第$i$天前30天购买一日票，对应的开销为$f[i-30]+costs[3]$

对于上述的每一种情况，我们取最小值即为$f[i]$的答案。

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let cost = [];
let days = [];
const choose = [1, 3, 7, 30]; // 不同的购买方案
const isplay = Array(366).fill(false);

rl.on('line', (line) => {
    const inputArray = line.split(' ').map(Number);

    if (cost.length === 0) {
        cost = inputArray;
    } else {
        days = inputArray;
        processInput();
    }
});

function processInput() {
    for (const x of days) {
        isplay[x] = true;
    }

    const f = Array(366).fill(10**9);
    f[0] = 0;

    for (let i = 1; i < 366; i++) {
        if (isplay[i]) { // 当天是游玩日
            for (let j = 0; j < 4; j++) { // 考虑四种不同的购买方案
                f[i] = Math.min(f[i], f[Math.max(0, i - choose[j])] + cost[j]);
            }
        } else {
            f[i] = f[i - 1];
        }
    }

    console.log(f[365]);
    rl.close();
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入并转为整数列表
        String costInput = scanner.nextLine();
        String daysInput = scanner.nextLine();
        String[] costArray = costInput.split(" ");
        String[] daysArray = daysInput.split(" ");
        List<Integer> cost = new ArrayList<>();
        List<Integer> days = new ArrayList<>();
        
        for (String str : costArray) {
            cost.add(Integer.parseInt(str));
        }
        
        for (String str : daysArray) {
            days.add(Integer.parseInt(str));
        }

        int[] choose = {1, 3, 7, 30};  // 不同的购买方案
        boolean[] isPlay = new boolean[366];
        
        // 标记游玩日期
        for (int x : days) {
            isPlay[x] = true;
        }

        int[] f = new int[366];
        Arrays.fill(f, (int)1e9);
        f[0] = 0;

        for (int i = 1; i < 366; i++) {
            if (isPlay[i]) {  // 当天是游玩日
                for (int j = 0; j < 4; j++) {  // 考虑四种不同的购买方案
                    f[i] = Math.min(f[i], f[Math.max(0, i - choose[j])] + cost.get(j));
                }
            } else {
                f[i] = f[i - 1];
            }
        }

        System.out.println(f[365]);
    }
}

Python

cost = list(map(int, input().split(' ')))
days = list(map(int, input().split(' ')))
choose = [1, 3, 7, 30]  # 不同的购买方案
isplay = [False] * 366

# 标记游玩日期
for x in days:
    isplay[x] = True

f = [10**9] * 366
f[0] = 0
for i in range(1, 366):
    if isplay[i]:  # 当天是游玩日
        for j in range(4):  # 考虑四种不同的购买方案
            f[i] = min(f[i], f[max(0, i - choose[j])] + cost[j])
    else:
        f[i] = f[i - 1]
print(f[365])

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> cost, days;
    int x;

    // 读取输入，将输入的数据存入days数组
    while (cin >> x) {
        days.push_back(x);
    }

    // 初始化cost数组，将days数组的前四个元素放入cost数组中
    for (int i = 0; i < 4; i++) {
        cost.push_back(days[0]);
        days.erase(days.begin());
    }

    int choose[] = {1, 3, 7, 30};  // 不同的购买方案
    bool isPlay[366] = {false};

    // 标记游玩日期
    for (int x : days) {
        isPlay[x] = true;
    }

    int f[366];

    // 将f数组初始化为正无穷
    fill(f, f + 366, 1e9);
    f[0] = 0; // 初始条件

    for (int i = 1; i < 366; i++) {
        if (isPlay[i]) {  // 当天是游玩日
            for (int j = 0; j < 4; j++) {  // 考虑四种不同的购买方案
                f[i] = min(f[i], f[max(0, i - choose[j])] + cost[j]);
            }
        } else {
            f[i] = f[i - 1]; // 当天不是游玩日，花费与前一天相同
        }
    }

    // 输出最终结果
    cout << f[365] << endl;

    return 0;
}

题目描述

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

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

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

小王计划在接下来玩计划所需要地最低消费。小王一年多次游玩该游乐园。小王计划地游玩日期将由一个数组给出。

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

输入描述

输入第一行为售票价格数组 $costs$ ；

输入第二行为小王计划游玩日期数组 $days$ 。

• $costs.length=4$ ，默认顺序为一日票、三日票、周票和月票。
• $1\le days.length\le 365，1\le days[i]\le 365$ ，默认顺序为升序。

输出描述

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

示例1

输入

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

输出

40

说明：

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