[CSP-J2 2019]纪念品 题解

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


发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据