Comment

Westbrook: 2024-05-31 19:03:13

采用动态规划的方法比较合适，其中dp指前i天旅游的花费价值，取最小值，那么对当前天进行划分，分别是买单日票，买七日票，买30日票
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 365 + 10; 
int costs[3];
int days[N];

int main() {
    int nums;
    cin >> nums;
    while (nums--) {
        int m;
        cin >> m;
        for (int i = 1; i <= m; i++) {
            cin >> days[i];
        }
        for (int i = 0; i < 3; i++) {
            cin >> costs[i];
        }

        int dp[N];
        memset(dp, 0, sizeof(dp));

        // 设置旅行天数数组，非旅行天数设为0
        bool travelDays[N] = { 0 };
        for (int i = 1; i <= m; i++) {
            travelDays[days[i]] = true;
        }

        for (int i = 1; i < N; i++) {
            if (!travelDays[i]) {
                dp[i] = dp[i - 1];
            }
            else {
                dp[i] = dp[i - 1] + costs[0]; // 一天通行证
                dp[i] = min(dp[i], dp[max(0, i - 7)] + costs[1]); // 七天通行证
                dp[i] = min(dp[i], dp[max(0, i - 30)] + costs[2]); // 三十天通行证
            }
        }
        cout << dp[365] << endl;
    }
    return 0;
}

许士杰: 2020-12-16 15:33:57

神奇的oj，突然就Accepted......