SSOJ2394潜水员
3851+
作者:crxis 发布:2017-10-25 分类:01背包
题目大意:潜水员带装备,越轻越好,有n个装备,分别有氧气ai、氮气bi,至少需要x氧气y氮气,装备最轻多少?
题目描述
潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸:一个为氧气,一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少? 例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量: 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入
第一行有2整数m,n(1<=m<=21,1<=n<=79)。它们表示氧,氮各自需要的量。 第二行为整数k(1<=k<=1000)表示气缸的个数。 此后的k行,每行包括ai,bi,ci(1<=ai<=21,1<=bi<=79,1<=ci<=800)3个整数。这些各自是:第i个气缸里的氧和氮的容量及汽缸重量。
输出
仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。
样例输入
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
样例输出
249
解题思路
二维费用的背包,只需要加一维记录不同氧气氮气的重量就行。每个装备只能选一次,因此从大到小枚举;由于没有限制重量,超过需求量也是可以的,超过需求量只需要记作最大值就行,因为最后输出的是最大值,而且更大值不会用到。整个过程中,只要保证用求过的数据来球后面的数据,而且后面的数据不会对前面的数据造成影响就行。(j从x枚举到0,k从y枚举到0,是因为这中间的任何一个氧气氮气值都可以继续添加装备。)