2018年2/3月月赛 Day1 行军(改) 题解
题目背景
再过十几天,人类远征军就要出发去讨伐星神(visitor)了。
正规勇者莉莉娅·阿斯普雷伊及一众准勇者们正在为行军问题而焦头烂额。
“这么多的粮草,还有那么远的路,这该怎么办啊?”莉莉娅抱怨道。
你能帮帮莉莉娅吗?
题目描述
从皇都到达星神居住地,这之间有无数座城市和无数条道路,将会消耗很多时间。
而为了保证军士们的生活,需要带上足够的粮草。
皇都共有n堆粮草可供选择,每堆粮草有重量p,体积q和价值w,而为了便于行军,莉莉娅只能选择不超过u重量且不超过v体积的粮草带走。
输入输出格式
输入格式
第一行,包含三个正整数,分别为粮草数量n,最大载重量u,最大体积v。
接下来n行,每行包含三个正整数p[i]、q[i]和w[i]。
第i+1行的p[i]表示第i堆粮草的重量,q[i]表示第i堆粮草的体积,w[i]表示第i堆粮草的价值。
输出格式
一行,输出能载的粮草的最大价值。
输入输出样例
输入样例#1:
1 | 6 10 10 |
输出样例#1:
1 | 4 |
输入样例#2:
1 | 10 16 24 |
输出样例#2:
1 | 26 |
说明
1<=n<=1000,1<=u<=1000,1<=v<=1000
所有数据不大于maxint
非常简单的一个二维约束的背包问题。解题方法详见这里
数据较大,最好scanf输入。
代码:
1 |
|