2019 纪念品 · 方案一逐天完全背包

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

今天买明天卖看成物品，每天做一次完全背包

2019
动态规划

正文

// CSP-J 2019 复赛 T3 · 纪念品
// 原题：https://oj.yecheng.tv/p/CSPJ2019C
// 题意：已知未来 T 天 N 种纪念品的价格，每天可买卖任意多次（当天卖的钱当天能再买），
// 最后一天必须全部卖出。问从 M 枚金币开始最多能变成多少。
//
// 方案一 · 逐天做一次完全背包（最贴近题意的写法）
// 关键转化一：「一直抱着不卖」和「今天卖掉、今天再用同样的价买回来」效果完全一样，
//             因为同一天的买价卖价是同一个数。于是每天只需要考虑「今天买、明天卖」。
// 关键转化二：第 i 天的第 j 种纪念品就是一个物品 —— 成本 P[i][j]，明天能卖 P[i+1][j]。
//             同一种想买多少个都行（金币够就买），这正是完全背包。
// dp[c] 表示：这天开始手上有 c 枚金币，做完当天买卖后最多能剩下多少。
// 完全背包一定要正序枚举容量 c（01 背包才是倒序），这样才能重复买同一种。

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

int p[105][105];   // p[i][j]：第 i 天第 j 种纪念品的价格

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];
    }

    for (int i = 1; i < T; i++) {
        // 每天重新开始：什么都不买时，手上的钱就是自己
        vector<long long> dp((size_t)money + 1);
        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];
            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 纪念品 · 方案一逐天完全背包