第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
[ZOJ1638]贪婪之岛
Grade | Open Time | Friday, 19 September 2014, 10:08 am | |
Discount | 0.8 | Time Discount | Friday, 26 September 2014, 10:08 am |
Allow late | Yes | Close Time | Friday, 26 September 2014, 10:08 am |
Input file | greedyisland.in | Output file | greedyisland.out |
【题目描述】
Gon和Killua正在进行一场贪婪之岛的游戏。游戏的目标是收集100张分散在整个游戏中的魔法卡片。一张卡片有三种能力:攻击,防御和特殊技能。每种能力的数值在[0,100]之间。每张卡只能使用一次,这一次只能使用一种能力。所有的卡片必须被储存在书——游戏的初始物品——中。书至多能储存50张卡片,因此Gon和Killua可以总共拥有之多100张卡片。现在Gon和Killua有n张卡片,并且他们想用A张来攻击,B张来防御,C张使用特殊技能(A+B+C<=100),如果n>A+B+C,他们就必须丢弃一些卡片。
他们想要知道“进攻”组卡片的进攻能力值和,“防御”组卡片的防御能力值和,“特殊技能”组卡片的特殊技能能力值和,这三者的最大和,以及在这个和达到最大时,所有卡片的所有能力和的最大值。
【输入格式】
输入包含多组数据。
输入文件的第一行有一个整数T(1<=T<=10),代表数据组数。
对于每组数据,第一行有一个整数n(n<=100000),第二行有三个整数A,B,C(A,B,C>=0,A+B+C<=n)。
接下来的n行每行有三个正整数,分别代表该卡片的进攻,防御和特殊能力值。
【输出格式】
对每组数据,输出一行两个正整数,即选取的A+B+C张卡片相应能力的之最大值,与相应能力和达到最大时所有能力和的最大值。
【样例输入】
2
3
1 1 1
100 0 0
0 100 0
0 0 100
4
1 1 1
12 32 44
33 48 37
37 38 33
46 79 78
【样例输出】
300 300
163 429
【提示】
样例解释:
第一组样例,选所有三张卡,第一张用于攻击,第二张用于防御,第三张用于特殊技能,相应能力值和是300,所有能力值和也是300.
第二组样例,选后三张卡,第二张用于防御,第三张用于攻击,第四章用于个数技能,相应能力值和是48+37+78=163,所有能力值和是(33+48+37)+(37+38+33)+(46+79+78)=429
【来源】
Author: JIANG, Jiefeng
Source: Zhejiang University Local Contest 2003