Luogu-P5662-纪念品

Posted on 2024-08-09 Edited on 2025-02-24 Word count in article: 615

题目 P5662 [CSP-J2019] 纪念品

题目描述

小伟突然获得一种超能力，他知道未来 $T$ 天 $N$ 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。

$T$ 天之后，小伟的超能力消失。因此他一定会在第 $T$ 天卖出所有纪念品换回金币。

小伟现在有 $M$ 枚金币，他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 $T, N, M$ ，相邻两数之间以一个空格分开，分别代表未来天数 $T$ ，纪念品数量 $N$ ，小伟现在拥有的金币数量 $M$ 。

接下来 $T$ 行，每行包含 $N$ 个正整数，相邻两数之间以一个空格分隔。第 $i$ 行的 $N$ 个正整数分别为 $P_{i,1},P_{i,2},\dots,P_{i,N}$ ，其中 $P_{i,j}$ 表示第 $i$ 天第 $j$ 种纪念品的价格。

输出格式

输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

思路：dp-完全背包

使用完全背包原因

无限购买
纪念品可以和钱任意转换（允许同时买入卖出）
每天开始时，
- 钱 $\rightarrow$ 容量
- 今天的价格 $\rightarrow$ 花费 $cost[i]$
- 明天的价格 $\rightarrow$ 价值 $value[i]$

dp表

和正常的完全背包一样，只不过 $dp[k]$ 表示钱的量为 $k$ 时的最大利润（不含成本）。含成本的方案见补充部分。

状态

初状态：均为 $0$ 。
状态转移方程：（此后均用 $\mathrm{minset}/\mathrm{maxset}(x, y)$ 代替 $x = \min/\max(x, y)$ ）
1
2
3
maxset(dp[k], dp[k - price[i][j]] + price[i + 1][j] - price[i + 1][j]);

money += dp[money];
末状态：最后的 $money$ 。

AC Code

// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

inline void maxset(int &t, int other) {
    t = max(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = 110;
const int M = 1e4+10;

int price[N][N];

int dp[M];

int main() {

    int t, n, m;
    cin >> t >> n >> m;
    for(int i = 1; i <= t; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> price[i][j];
        }
    }
    int money = m;
    for(int i = 1; i < t; i++) {
        memset(dp, 0, sizeof dp);
        for(int j = 1; j <= n; j++) {
            for(int k = price[i][j]; k <= money; k++){
                maxset(dp[k], dp[k - price[i][j]] + price[i + 1][j] - price[i][j]);
            }
        }
        money += dp[money];
    }
    cout << money << endl;
    return 0;
}

补充

使用含成本的dp

含成本的状态

初状态：均为 $money$ 。

状态转移方程：

1
2
3

maxset(dp[k], dp[k - price[i][j]] + price[i + 1][j] - price[i + 1][j]);

money = dp[money];

末状态：最后的 $money$ 。

AC Code

// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

inline void maxset(int &t, int other) {
    t = max(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = 110;
const int M = 1e4+10;

int price[N][N];

int dp[M];

int main() {

    int t, n, m;
    cin >> t >> n >> m;
    for(int i = 1; i <= t; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> price[i][j];
        }
    }
    int money = m;
    for(int i = 1; i < t; i++) {
        memset(dp, 0, sizeof dp);
        for(int k = 0; k <= money; k++) {
            dp[k] = money;
        }
        for(int j = 1; j <= n; j++) {
            for(int k = price[i][j]; k <= money; k++){
                maxset(dp[k], dp[k - price[i][j]] + price[i + 1][j] - price[i][j]);
            }
        }
        money = dp[money];
    }
    cout << money << endl;
    return 0;
}