P5662 纪念品
2024-08-25 02:51:41
P5662 纪念品
题解
拿到题目想到DP,但是就是不知道咋写
后来证实这是个背包DP(最近整理背包白整了
我们观察这道题目的特殊之处:
也就是说,对于手中的物品,我们可以今天买了然后明天早上接着卖出去,当然如果你想一直持有物品的话还可以明天接着再买回来,这样我们在每天进行决策的时候就不用考虑手中持有物品了,因为你手里都是钱,这和第一天情况类似嘛不
然后每一天都是一个新的开始,相似于前一天,然后我们仍然可以按照前一天的做法处理今天,今天也就是你有n个物品,每个物品可以买多个,然后考虑明天早上把它们全部卖出最多可以得到多少钱,然后用明天早上卖出的钱作为新的资本来进行明天的决策
于是我们可以想到完全背包
dp [ i ][ j ][ k ] 到了第 i 天,第 j 个物品,手中还剩下 k 元钱,明天早上把手中的物品全部卖出可以得到的最大利润
dp [ i ][ j ][ k ] = max ( dp [ i ][ j ][ k ] , dp [ i ][ j-1 ][ k - p[ i ][ j ] + p[ i+1 ][ j ] - p[ i ][ j ] )
然后降一维 dp [ k ]
dp [ k ] = max ( dp [ k ] , dp [ k - p[ i ][ j ] ] + p[ i+1 ][ j ] - p[ i ][ j ] )
我们选取今天的最大利润加上今天的原资本(当然如果今天全赔本肯定就是直接选取原资本作为下一天开始的资本),作为下一天开始的资本
注意 dp 数组设置的是利润,所以每次开始新的一天都要清零 dp 数组
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue> using namespace std; typedef long long ll; inline int read()
{
int ans=;
char last=' ',ch=getchar();
while(ch<''||ch>'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
} int t,n,m,ans=;
int p[][];
int dp[]; int main()
{
t=read();n=read();m=read();
for(int i=;i<=t;i++)
for(int j=;j<=n;j++)
p[i][j]=read();
ans=m;
for(int i=;i<=t;i++){
memset(dp,,sizeof(dp));
for(int j=;j<=n;j++)
for(int k=p[i][j];k<=m;k++){
dp[k]=max(dp[k],dp[k-p[i][j]]+p[i+][j]-p[i][j]);
}
for(int j=;j<=m;j++) ans=max(ans,dp[j]+m);
m=ans;
}
printf("%d\n",m);
return ;
}
最新文章
- toArray(),toJson(),hidden([ ]),visible([ ])
- 认识DOM和一些方法
- HYSBZ 2243
- 安装Arch Linux
- unity3d Light Probe Group图解超详细使用方法
- jquery选择器之内容选择器
- 通过FileWatcher,监听通过web上传的图片,并进行压缩
- 8.LNMP环境的配置
- select/**/*/**/from/**/RegSite
- Java内存泄漏分析与解决方案
- Controller@实现Controller的两种形式
- xhr的send方法以及node如何处理get和post数据
- HTTP协议的请求和响应学习
- Redis相关命令及Jedis的demo(转)
- 你不能错过.net 并发解决方案
- springboot实现数据库中数据导出Excel功能
- Python——使用高德API获取POI(以深圳南山医疗保健服务POI为例)
- iOS异常捕获和处理
- [Swift]LeetCode450. 删除二叉搜索树中的节点 | Delete Node in a BST
- 爬起点小说 day02