Nowcoder Girl 初赛 T5

Nowcoder Girl 初赛第五题

来源

Nowcoder Girl 初赛第五题

题面

(n(1<=n<=10000))件武器，每件武器对于属性有加成，一共五种属性。若使用其中的(x)件武器，每个属性获得的加成是(x)件武器最大的加成值。要求取出(k(1<=k<=n))件武器，使得所有属性获得的加成值之和最大。输出加成值之和的最大值。

样例

INPUT

4 2
30 30 30 30 0
50 0 0 0 0 
0 50 0 50 10
0 0 50 0 20

OUTPUT

170

INPUT

4 3
30 30 30 30 0
50 0 0 0 0 
0 50 0 50 10
0 0 50 0 20

OUTPUT

220

题解

• 如果对于每个属性，都取加成值最大的那件武器，那么最后会取(t)件武器，易知(1<=t<=5)。
• 如果(k>=t)，最后的答案就是取这(t)件武器，其他(k-t)件随便取。
• 如果(k<t)：
  • 可以用(5)位的(bitmask)表示取了哪几个属性，(bitmask)一共有(2^5=32)个取值。
  • 对于每个取值，计算取哪件武器会使得选中的这几个属性的加成之和最大。
  • 最后取了(t)件武器，易知(1<=t<=32)。
  • 那么最后的(k)个答案应该在这(32)件武器中取。
  • 证明：
    • 很容易知道，最后取出的(k)件武器只有(t)件是有贡献的，(1<=t<=5)。
    • 假设有一件武器贡献了(1、3、4)这三个属性，那么它肯定是所有武器中(1、3、4)这三个属性之和最大的武器。如果不是的话，我们可以取是的那件武器，这样最后的答案会更大。
    • 然后每一类属性之和最大的武器我们都预处理出来了，(k)又小于(5)，随便(k)个循环就可以搞定了。