2019 纪念品 · 方案二砍掉不赚钱物品

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1172 字

跳过不涨价的物品，一维数组滚动

2019
动态规划

正文

// CSP-J 2019 复赛 T3 · 纪念品（方案二 · 更紧凑的满分写法）
// 原题：https://oj.yecheng.tv/p/CSPJ2019C
//
// 方案二 · 砍掉不赚钱的物品 + 直接把收益并回本金
// 改进一：明天不比今天贵的纪念品，买了只会亏，直接 continue 跳过，常数更小。
// 改进二：不必保留「哪一天」这一维 —— 每天做完背包后把结果写回 money，
//         只用一个一维数组滚动，代码更短、也更省内存。
// 复杂度：时间 O(T * N * M)，空间 O(M)。

#include <bits/stdc++.h>
using namespace std;

int p[105][105];

int main() {
    freopen("souvenir.in", "r", stdin);
    freopen("souvenir.out", "w", stdout);

    int T, N;
    long long money;
    cin >> T >> N >> money;
    for (int i = 1; i <= T; i++) {
        for (int j = 1; j <= N; j++) cin >> p[i][j];
    }

    vector<long long> dp;
    for (int i = 1; i < T; i++) {
        dp.assign((size_t)money + 1, 0);
        for (long long c = 0; c <= money; c++) dp[(size_t)c] = c;

        for (int j = 1; j <= N; j++) {
            int cost = p[i][j];
            int gain = p[i + 1][j];
            if (gain <= cost) continue;          // 不赚钱，不碰
            for (long long c = cost; c <= money; c++) {
                dp[(size_t)c] = max(dp[(size_t)c], dp[(size_t)(c - cost)] + gain);
            }
        }
        money = dp[(size_t)money];
    }

    cout << money << "\n";
    return 0;
}

2019 纪念品 · 方案二 砍掉不赚钱物品

正文

CSP-J 标程 · 复赛真题的其它内容

2019 纪念品 · 方案二砍掉不赚钱物品