复赛三:纪念品(souvenir)

洛谷:P5662
OJ : P4964

算法逻辑分析:

  1. 输入处理
    • 首先读取天数 t、纪念品种类 n 以及初始的金币数量 m。然后读取每种纪念品在每天的价格。
  2. 动态规划的思想
    • 定义 f[j] 表示用 j 枚金币能获得的最大利润。我们采用完全背包的方式进行遍历,从小到大更新金币数 j
    • 对于每一种纪念品,在每一天,如果价格是较低的,则可以考虑买入并在第二天高价卖出,进而计算所获得的利润。
    • 状态转移方程 f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]),表示若当前持有金币数 j,若购买第 i 种纪念品并在下一天卖出,能否获得更大的利润。
  3. 盈利累计
    • 每一天结束时,将这一天通过交易获得的最大盈利 f[m] 加到现有金币数 m 上,作为下一天的初始金币数,继续进行接下来的买卖操作。
  4. 最后输出
    • 最终输出经过 t-1 天交易后的最大金币数。

总结:

该算法本质上是一个基于完全背包的动态规划问题,通过每天进行背包转移,计算在未来的买卖中所能获得的最大利润。

代码实现:

 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 <iostream>
#include <memory.h>  // 包含 memset 函数头文件
using namespace std;

const int N = 101;   // 最大纪念品种类数
const int M = 10001; // 最大金币数量

int n, m, t;  // n: 纪念品种类, m: 初始金币数量, t: 天数
int price[N][N], f[M];  // price[i][j] 表示第 j 天第 i 种纪念品的价格, f[j] 表示用 j 枚金币可以获得的最大盈利

int main(){
    freopen("souvenir.in","r",stdin);
    freopen("souvenir.out","w",stdout);
    // 读取输入的天数 t、纪念品种类 n 和初始金币数量 m
	cin >> t >> n >> m;
    
    // 读取每种纪念品在每一天的价格,注意这里的 i 表示天数,j 表示纪念品种类
	for(int i = 1; i <= t; i++)
		for(int j = 1; j <= n; j++)
			cin >> price[j][i];
          // price[j][i] 表示第 i 天第 j 种纪念品的价格

    // 循环从第 1 天到第 t-1 天,处理买卖操作
	for(int k = 1; k < t; k++)
	{
		// 每一轮交易前都需要将动态规划数组 f 置零,表示当前没有盈利
		memset(f, 0, sizeof f);

        // 遍历每种纪念品
		for(int i = 1; i <= n; i++) {
            // 完全背包的思想:正序遍历金币数 j,从商品价格开始,尝试用 j 枚金币进行交易
            // 这里表示从金币数 price[i][k] 开始,直到最大金币数 m
			for(int j = price[i][k]; j <= m; j++) {
				// 状态转移方程:f[j] 表示用 j 枚金币所能获得的最大盈利
				// f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k])
				// 意思是如果用 j 枚金币买入第 i 种纪念品,再在第 k+1 天卖出,计算出能否获得更大的盈利
				f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);
			}
		}

		// 在每一轮结束时,m 需要加上 f[m],即这一天买卖操作获得的最大盈利,进入下一轮
		m += f[m];
	}

    // 最终输出金币数量,即经过 t-1 天后的最大金币数量
	cout << m;
	return 0;
}
Scroll to Top