题目描述
小伟突然获得一种超能力，他知道未来 $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$ 时的最大利润（不含成本）。含成本的方案见补充部分。
状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#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$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#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;
}
|