纪念品 题解
2023-09-09 11:43:58
发布于:广东
看到题目就感觉到一定是动态规划了,但是怎么定义状态呢?到每一天的时候,手里不同纪念品的数量有很多,要是每种情况都存下来,状态爆炸多,必死无疑啊。
这题感觉跟买卖股票很像啊,回忆一下我平时怎么炒(pei)股(qian)的呢?就是频繁交易嘛,今天买了,明天看到涨就卖,看到跌了也忍不住要卖。可惜我没有小伟的超能力啊,这里实名羡慕。
这题题面有一句关键的话,“当日购买的纪念品也可以当日卖出换回金币”!这句话可以帮我们简化状态,因为如果一个纪念品,你想连续持有若干天,可以看做第一天买,第二天早上立刻卖掉,然后第二天买回来,第三天早上立刻卖掉,然后第三天买回来……所以我们就不需要记录每天手里持有多少纪念品了,统一认为我们今天买的纪念品,明天早上就立刻卖掉。明天又是新的一天,用所有的现金,进行新的决策就好了。
我们定义一个三维的数组,dp[i][j][k]dp[i][j][k]表示第i天,我们考虑到第j个物品的时候,手里现金还有k元的时候,明天早上全卖掉能拿到的金币数。类似完全背包的思路,就可以写递推了。我们用price[i][j]price[i][j]表示第i天第j个物品的价格,外层循环i,里层循环每个物品j,手里留k元现金,则
dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k+price[i][j]]+price[i+1][j]-price[i][j])dp[i][j][k]=max(dp[i][j][k],dp[i][j−1][k+price[i][j]]+price[i+1][j]−price[i][j])
表示第j个物品如果要了,手里现金少了price[i][j]price[i][j],但是期望明天早上的收益多了price[i+1][j]-price[i][j])price[i+1][j]−price[i][j])
j循环完一遍以后,在收益里面取最大值,变成下一天的开始金币数。
但是这样开三维数组会炸空间,没关系,见过世面的我根本不慌。因为从第i天传递到第i+1天,只需要传递一个数字,即最大收益。如果第二题早上都卖掉有多重选择,为啥不选最赚钱的呢,是吧?所以第一个维度可以压掉。第二个维度,多重背包可以循环的时候控制循环方向压一维,相信学过完全背包的同学都会。所以其实数组只有一维就够了,表示手里现金数,按照题目说明,不会超过10000
其余细节见代码注释:
AC代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 105;
//dp[k]表示手里剩k元现金的时候,明天早上都卖了以后的钱数
//price[i][j]表示第i天第j件物品的价格
int dp[10005], price[MAXN][MAXN];
int main() {
int t, n, m, ans;
scanf("%d%d%d", &t, &n, &m);
//先输入
for (int i = 1; i <= t; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%d", &price[i][j]);
}
}
//第一天早上手里有m元
ans = m;
for (int i = 1; i < t; ++i) {
//先把数组赋值为负无穷
memset(dp, ~0x3f, sizeof(dp));
//什么都不买,今天早上有ans元,明天早上也是ans元
dp[ans] = ans;
//枚举第j个物品
for (int j = 1; j <= n; ++j) {
//手里有k元的时候,去推明天早上的钱
for (int k = ans; k >= price[i][j]; --k) {
//买一件物品,现金减少,赚一份差价,完全背包倒着循环
dp[k - price[i][j]] = max(dp[k - price[i][j]], dp[k] + price[i + 1][j] - price[i][j]);
}
}
//找一下明天早上收益最大
int ma = 0;
for (int j = 0; j <= ans; ++j) {
ma = max(ma, dp[j]);
}
//明天早上就有这么多钱了,继续赚钱
ans = ma;
}
cout << ans << endl;
return 0;
}
这里空空如也
有帮助,赞一个