华师一附中OI组

标题: P1759 通天之潜水 [打印本页]

作者: admin 时间: 2018-5-21 12:25
标题: P1759 通天之潜水
https://www.luogu.org/problemnew/show/P1759
题目描述
在猴王的帮助下，小A终于走出了这篇荒山，却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船，但好在小A有n个潜水工具。由于他还要背重重的背包，所以他只能背m重的工具，又因为他的力气并不是无限的，河却很宽，所以他只能背有v阻力的工具。但是这条河下有非常重要的数据，所以他希望能够停留的时间最久。于是他找到了你，让你告诉他方案。

输入输出格式
输入格式：
三个数m,v,n如题目所说

接下来n行，每行三个数ai,bi,ci分别表示所含的重力，阻力，能够支撑的时间

输出格式：
第一行一个数，表示最长的时间

接下来一行，若干个数，表示所选的物品

输入输出样例
输入样例#1：
100 100 3
50 60 289
40 10 116
50 50 106
输出样例#1：
405
1 2
说明
1<=m,v<=200,n<=100

数据保证一定有方案。

若有多种方案，输出前面尽量小的方案。

欢迎光临华师一附中OI组 (http://hsyit.cn/)