线上OJ

一本通：http://ybt.ssoier.cn:8088/problem_show.php?pid=1984 (opens in a new tab)

洛谷：https://www.luogu.com.cn/problem/P5662 (opens in a new tab)

题中关键句

1、“纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量”：说明同一种商品在同一天买卖的价格相同，即同一种商品在同一天内不管你买卖多少轮，总金币数量不变。

2、“任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品，注意同一个纪念品可以在同一天重复买”：说明是类似完全背包。

题目分析

1、观察数据范围，发现“对于 10% 的数据，T=1” 。如果只有一天，那不管怎么买卖总金币数量都不会变，此时读入的金币数量 M 即为最终结果，直接输出即可。（10分轻松拿到~~）

2、同样，观察数据范围，发现“对于 15% 的数据，T=2, N≤100”。即，对于 T = 2 的数据，说明就是第一天买进，第二天卖出，只有一轮。而题中要求输出最后的金币数量最大化，这就变成了一个典型的完全背包问题，可以直接套用公式。要注意的是：

2.1、原公式中第 i 种物品的价值 val[i] 在本题中表现为价差（即 p[2][i] - p[1][i]：第 i 种商品第2天的价格-第1天的价格 ）

2.2、原公式中第 i 种物品的重量 v[i] 在本题中表现为第1天的购买成本，就是 p[1][i] 这样，只要套用公式，又有15分轻松拿到

3、当 T=1 和 T=2 的思路捋清后，我们发现，每多一天其实就是在前一天的基础上再多做一轮完全背包。所以，只要在 T=2的代码外面，再封装 N-1轮循环即可（N 天就是 N-1 轮）。至此，100%分数全部包含。

核心思想

1、标准二维 dp方程：完全背包公式

$dp[i][j] = max( dp[i - 1][j], dp[i][j - v[i]] + val[i] )$;

1.1、其中 dp[i][j]表示前 i 种纪念币，在总可用金币数量为 j 时能赚到的最大金币。

1.2、val[i]: 第i种纪念币在某次完全背包中的价值（本题中就是买进卖出的价差）

1.3、v[i]: 第 i 种纪念币在某次完全背包中的重量（本题中就是购买成本）

2、压缩后的一维 dp方程（只保留第二位）：

$dp[j] = max( dp[j], dp[j - v[i]] + val[i] )$;

2.1、压缩后的完全背包只考虑第二个参数，dp[j] 表示背包容量为 j 时能赚到的最大金币。（val[i] 和 v[i] 同上）

2.2、压缩一维 dp 的内层 for 循环从v[i]开始

2.3、由于dp只有一维，所以每一轮完全背包之前，要先初始化dp数组

题解代码

#include <bits/stdc++.h>
using namespace std;
 
int T, N, M;
int p[105][105];	//  p[t][i]: 第t天第i个纪念品的价格  
int dp[105][10005];	// dp[i][j]: 前i种纪念币，总可用金币数量为j时能赚到的最大金币 
					// 故本题输出内容为: T-1轮后，dp[N][M] + 前一天结束时的金币数量 
// 将每两天看成一次完全背包，直接套完全背包公式 dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i]);					
int val[105];		// val[i]: 第i种纪念币在某次完全背包中的价值（本题中就是价差） 
int v[105];			// v[i]:第i种纪念币在某次完全背包中的重量（本题中就是购买成本） 
 
int main()
{
    cin >> T >> N >> M;
	for(int t = 1; t <= T; t++)
		for(int i = 1; i <= N; i++)
			cin >> p[t][i]; 
	
    for(int t = 1; t <= T - 1; t++)	
    {    	
    	for(int i = 1; i <= N; i++)
		{
			val[i] = p[t + 1][i] - p[t][i];	// 第i种纪念币在第t轮完全背包计算中的价值 
			v[i] = p[t][i];					// 第i种纪念币在第t轮完全背包计算中的成本
			for(int j = 1; j <= M; j++)
			{
				if(j >= v[i])	// 如果可用总金币数量 j 多于第i种纪念币的购买成本
					dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + val[i]); 
				else			// 如果可用总金币数量 j 少于第i种纪念币的购买成本 
					dp[i][j] = dp[i-1][j];	// 则买不起第i种纪念币，所以 dp[i][j]继承 dp[i-1][j] 
			} 
		} 				
		M += dp[N][M];		
	}
	
    cout << M << endl;
    return 0;
}