[CSP-J2 2019]纪念品 题解

题目地址：洛谷：P5662 纪念品 – 洛谷 | 计算机科学教育新生态

题目描述

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

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

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

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

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

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

题意简述

有 $N$ 种纪念品，给出 $T$ 天内每种纪念品的价格，每天可以以当日价格买和卖纪念品，初始时有 $M$ 钱，求买卖方案使最终钱数最大。

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

样例 #1

输入样例 #1：

6 1 100
50
20
25
20
25
50

输出样例 #1：

305

样例 #2

输入样例 #2：

3 3 100
10 20 15
15 17 13
15 25 16

输出样例 #2：

217

数据范围

对于 $10\%$ 的数据，$T = 1$。

对于 $30\%$ 的数据，$T \leq 4, N \leq 4, M \leq 100$，所有价格 $10 \leq P_{i,j} \leq 100$。

另有 $15\%$ 的数据，$T \leq 100, N = 1$。

另有 $15\%$ 的数据，$T = 2, N \leq 100$。

对于 $100\%$ 的数据，$T \leq 100, N \leq 100, M \leq 10^3$，所有价格 $1 \leq P_{i,j} \leq 10^4$，数据保证任意时刻，小明手上的金币数不可能超过 $10^4$。

题解

既然同一天的买和卖是可以任意进行的，则持有的一个纪念品在某一天不参与买卖，等价于某一天卖了一个纪念品又买了一个。因此，在某一天买纪念品之前可以先把持有的纪念品全都卖掉，然后再决定如何买纪念品。

有了上述对模型的简化后，容易设计出 DP 状态为 $f(i, j, k)$ 表示第 $i$ 天时，考虑第 $j$ 个纪念品，手上还剩 $k$ 钱时后一天卖出后得到的最多钱数，容易获得以下转移：

$$ f(i, j, k) = \max \{ f(i, j-1, k+P_{i, j}) – P_{i, j} + P_{i+1, j} \} $$

DP 的初始值为该天不进行买卖， $ f(i, j, k) = k $。

接下来对上述模型进行优化。首先发现转移与第一维没关系，直接删去也不会影响正确性。然后转移的第二维只与比 $j$ 小的状态相关，因此用逆序转移（类似完全背包的转移）可以保证正确性，第二维也同样可以删去。最终的 DP 状态只保留了一维。

当开始计算第 $i+1$ 天时，这一天的初始钱数为前一天的最大钱数 $m$ ，因此直接令 $f(m)=m$ （这一天不买纪念品，钱数不发生变化）作为 DP 初始值即可。其他状态的初始值应设为极小值 $0$ 。

令 $C = 10^4$ 表示可能的最大钱数，则该算法的复杂度为 $O(N^2C)$ 。

代码

// Code by KSkun, 2019/11
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <utility>

typedef long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
	static char buf[100000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
		? EOF : *p1++;
}

inline LL readint() {
	LL res = 0, neg = 1; char c = fgc();
	for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
	for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
	return res * neg;
}

inline char readsingle() {
	char c;
	while(!isgraph(c = fgc())) {}
	return c;
}

const int MAXN = 105;

int t, n, m, p[MAXN][MAXN], f[10005];

int main() {
	t = readint(); n = readint(); m = readint();
	for (int i = 1; i <= t; i++) {
		for (int j = 1; j <= n; j++) {
			p[i][j] = readint();
		}
	}
	int ans = m;
	for (int i = 1; i <= t; i++) {
		memset(f, 0, sizeof(f));
		f[ans] = ans;
		for (int j = 1; j <= n; j++) {
			for (int k = ans; k >= p[i][j]; k--) {
				f[k - p[i][j]] = std::max(f[k - p[i][j]], f[k] - p[i][j] + p[i + 1][j]);
			}
		}
		int mx = 0;
		for (int i = 0; i <= ans; i++) {
			mx = std::max(mx, f[i]);
		}
		ans = mx;
	}
	printf("%d", ans);
	return 0;
}