Comment

harkerhand: 2025-04-25 18:12:51

好简单的dp
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int m;
    cin >> m;
    vector<int> days(m);
    for (int i = 0; i < m; i++)
    {
        cin >> days[i];
    }
    vector<int> costs(3);
    cin >> costs[0] >> costs[1] >> costs[2];
    vector<int> dp(366, 0);
    for (int i = 1; i < 366; i++)
    {
        if (binary_search(days.begin(), days.end(), i))
        {
            dp[i] = min({dp[i - 1] + costs[0], dp[max(0LL, i - 7)] + costs[1], dp[max(0LL, i - 30)] + costs[2]});
        }
        else
        {
            dp[i] = dp[i - 1];
        }
    }
    cout << dp[365] << endl;
}
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

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......