♐ CSP_J 组真题
2019年
3. 纪念品

线上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[i1][j],dp[i][jv[i]]+val[i])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[jv[i]]+val[i])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数组

题解代码

解法一、标准二维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;
}