题解：P5662 [CSP-J2019] 纪念品

P5662 [CSP-J2019] 纪念品题解

前言

虽然这道题的题解提交通道已经关闭，但是这道题实在是值得写一篇题解。我看完题目以后一脸懵b，听完老师的讲解才知道如此简单。

思路

完全背包。既然是背包，就要找到质量

w

和价值

v

。对于本题，

w

表示纪念品的价格。

w

每天都会变，因此我们将

w

扩大到2维，即

w_{i,j}

表示第

i

天第

j

件纪念品的价格，也就相当于题目中所给的

P

数组。问题来了，什么表示

v

？这就需要我们将问题简化：假设第

i

天买完以后第

i+1

天立刻卖出，即使第

i+2

天卖出赚的更多，也可以选择第

i+1

天再买，第

i+2

天卖出。于是，我们定义

v_{i,j}=w_{i+1,j}-w_{i,j}

，表示第

i

天买入第

j

件纪念品后第

i+1

天卖出的收益。这样，完全背包外面再套一层循环表示天数，每天收益加一起，本题结束。

状态转移方程

dp[k]=max(dp[k],dp[k-w[i][j]]+(w[i+1][j]-w[i][j]))

代码

CPP

#include <bits/stdc++.h>
using namespace std;
//注意dp数组不是开到m，因为总钱数每天都会变
//题面： 对于100%的数据，小伟手上的金币数不可能超过10^4
int w[110][110],dp[10010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t,n,m;
	cin>>t>>n>>m;
	for (int i=1;i<=t;i++){
		for (int j=1;j<=n;j++){
			cin>>w[i][j];
		}
	}
	//从第1天到第t-1天进行交易，第t天只负责卖
	for (int i=1;i<t;i++){
		memset(dp,0,sizeof dp);
		//完全背包，n件物品，m枚金币
		for (int j=1;j<=n;j++){
			for (int k=w[i][j];k<=m;k++){
				//dp[k]在第i天买入第j件物品后的最大总钱数
				//dp[k-w[i][j]]在第i天买入第j件物品前的最大总钱数
				//w[i+1][j]-w[i][j]在第i天买入第j件物品后在第i+1天卖出的最大收益
				dp[k]=max(dp[k],dp[k-w[i][j]]+(w[i+1][j]-w[i][j]));
			}
		}
		//今天的总钱数再加上明天的收益就是明天的起始钱数
		m+=dp[m];
	}
	cout<<m;
	return 0;
}

双倍经验

P2938 [USACO09FEB] Stock Market G

题解：P5662 [CSP-J2019] 纪念品

文章操作

P5662 [CSP-J2019] 纪念品题解

前言

思路

状态转移方程

代码

双倍经验

相关推荐

评论

题解：P5662 [CSP-J2019] 纪念品