首页 > 分享 > 题解 P5662 [CSP

题解 P5662 [CSP

花匠小妙招
2024-09-16 22:27

题目传送门

做到这个题的时候人都傻了，被鹏哥批了一顿后，直接大叫：“ woc!" role="presentation">woc! ，这不就一完全背包吗！”

好吧，让我们看看这个题怎么和背包扯上关系的。

进入正题

第一眼，嗯，dp。

想了一会以后发现想不出来，好吧，看一下部分分。

T=1" role="presentation">T=1 ，直接就是 m" role="presentation">m ，没什么用（蹭点分还是很香的）

再看，诶，T=2" role="presentation">T=2，好家伙，看一下买哪个赚的最多，直接买了，如果还有余钱买第二赚的，继续买……当买不了了，第二天统统卖掉，此时就可以得到答案。

再想一想，如果把这两天结束后的钱当做新一轮开始时的本钱，是不是只要一直重复同样的步骤就能得出答案？

完全没毛病啊！而且只要保证每一轮得到最大的钱数（局部最优解），就一定可以保证整体的最优解。

注意到题目中有这句话：“每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。”也就是说，我们可以每天先把手头的纪念品全卖掉，然后重新购买，完美契合上面的想法。

如何满足局部最优解呢？物品数量不限，总价值有限制，这不就一完全背包吗！

把当前拥有的钱数看做背包的体积。

把物品的价格看做取该物品的代价。

把物品在第二天卖掉时赚的钱当做价值。

完美的一个完全背包！

细节看代码：

#include<bits/stdc++.h> #define rd(n) scanf("%d",&n); #define F(i,a,b) for(register int i=a;i<=b;i++) using namespace std; const int N=1e4+10; int t,n,m,p[1001][1001],dp[N]; int main(){rd(t)rd(n)rd(m)F(i,1,t){F(j,1,n){rd(p[j][i])}}F(k,1,t-1){memset(dp,0,sizeof(dp));//每一轮开始前清空F(i,1,n){F(j,p[i][k],m){//完全背包，正着做dp[j]=max(dp[j],dp[j-p[i][k]]+p[i][k+1]-p[i][k]);//p[i][k+1]-p[i][k]是两天的差价（即选该物品得到的价值）}}m+=dp[m];//将当前一轮结束时的局部最优解转化为下一轮的本金}printf("%d",m); return 0; }