OI题库

【题目描述】

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

ZOJ 1638 Greedy Island