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

总结：

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

代码实现：

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

Previous Topic

Back to Lesson

Next Quiz