洛谷——P1759 通天之潜水
2024-08-26 11:21:51
题目背景
直达通天路·小A历险记第三篇
题目描述
在猴王的帮助下,小A终于走出了这篇荒山,却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船,但好在小A有n个潜水工具。由于他还要背重重的背包,所以他只能背m重的工具,又因为他的力气并不是无限的,河却很宽,所以他只能背有v阻力的工具。但是这条河下有非常重要的数据,所以他希望能够停留的时间最久。于是他找到了你,让你告诉他方案。
输入输出格式
输入格式:
三个数m,v,n如题目所说
接下来n行,每行三个数ai,bi,ci分别表示所含的重力,阻力,能够支撑的时间
输出格式:
第一行一个数,表示最长的时间
接下来一行,若干个数,表示所选的物品
输入输出样例
说明
1<=m,v<=200,n<=100
数据保证一定有方案。
若有多种方案,输出前面尽量小的方案。
大体题意:
你有n件物品,每件物品有两个限制属性重力m.阻力v,还有可使用时间c,你有最大承受重力和最大承受阻力,问你最多能坚持多长时间?并输出你所选择的物品。
解题报告:
这就是传说中的二维费用的背包问题,简单讲转移方程就是01背包增加了一维:
$F[j,k]=max{F[j][k],F[j-m[i]][k-v[i]]}$ $F[j][k]$表示重量为j,阻力为k时最多的持续时间。
可以二维费用背包求解时间,dfs求解方案
注意:函数与库的调用
#include<stdlib.h>
exit(0)
第一次提交由于这个CE了
#include<iostream>
#include<cstdio>
#include<stdlib.h> #define N 1011
using namespace std; int m,v,n,a[N],b[N],c[N],f[N][N],an[N]; void print(int sum){
for(int i=;i<=sum;i++) printf("%d ",an[i]);
return;
} void dfs(int k,int tk,int M,int V,int T){
if(M>m||V>v||T>f[m][v]) return;
if(T==f[m][v]){
print(tk-);
exit();
}
for(int i=k;i<=n;i++){
an[tk]=i;
dfs(i+,tk+,M+a[i],V+b[i],T+c[i]);
dfs(i+,tk,M,V,T);
}
} int main()
{
scanf("%d%d%d",&m,&v,&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(int i=;i<=n;i++){
for(int j=m;j>=a[i];j--){
for(int k=v;k>=b[i];k--){
f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+c[i]);
}
}
}
printf("%d\n",f[m][v]);
dfs(,,,,);
return ;
}
显然dfs是超时的,80。
如何记录路径呢?
$an[j][k][p]$记录重量为j,阻力为k时第p件物品是谁。
#include<iostream>
#include<cstdio>
#include<stdlib.h> #define N 205
using namespace std; int m,v,n,a[N],b[N],c[N],f[N][N],an[][][]; int main()
{
scanf("%d%d%d",&m,&v,&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(int i=;i<=n;i++){
for(int j=m;j>=a[i];j--){
for(int k=v;k>=b[i];k--){
if(f[j][k]<f[j-a[i]][k-b[i]]+c[i]){
f[j][k]=f[j-a[i]][k-b[i]]+c[i];
for(int p=;p<=an[j-a[i]][k-b[i]][];p++){
an[j][k][p]=an[j-a[i]][k-b[i]][p];
}
an[j][k][]=an[j-a[i]][k-b[i]][]+;
an[j][k][an[j][k][]]=i;
}
}
}
}
printf("%d\n",f[m][v]);
for(int i=;i<=an[m][v][];i++) printf("%d ",an[m][v][i]);
return ;
}
背包学习
最新文章
- 【转】段错误调试神器 - Core Dump详解
- ASP.Net 在Update Panel局部刷新后 重新绑定JS方法
- android 断点下载---XUtils
- zabbix3.2安装graphtree3.0.4
- Linux 小工具学习之(1)——Wget十例[翻译]
- C#.NET 大型信息化系统集成快速开发平台 - 手机短信开发接口 4.0
- php header函数详解
- MCS51系列单片机实用技术部分课件
- onmousemove和onmouseout事件的调用,和js使用双引号、单引号的时候应该注意的问题
- linux编译相关知识
- java中关于public class
- 关于javascript中setTimeout()和clearTimeout()的疑惑。
- Codeforces 474D Flowers dp(水
- 卡特兰数(Catalan)简介
- A计划
- Install OpenCV 3.0 and Python 2.7+ on OSX
- 使用ADO.NET操作数据库
- linux文件查找find命令
- java 反射模式
- IWMS后台上传文章,嵌入音频文件代码
热门文章
- HDU 5090 Game with Pearls(二分匹配)
- Java - 对象(object) 具体解释
- cocos2d-x 多触点监听
- 3736 【HR】万花丛中2
- cacheed 限制 4节点 3000万 es 批量删除 shell脚本练习 elasticsearch_action
- X86架构下Linux启动过程分析
- 在Sql Server触发器中判断操作是Insert还是Update还是Delete
- eclipse高亮选中属性以及更改颜色
- codeforces 939E Maximize! 双指针(two pointers)
- 【模板】 倍增lca