题目描述
美丽的牛家庄受到了外星人的侵略, 勇敢的妞妞要上战场抵御侵略。
在妞妞上战场前, 村长牛牛给了妞妞N件装备, 妞妞需要选择其中的K件,装备在身上提升自己的战斗力。每件装备有5种属性增幅值,对于第i件装备它的属性增幅值为(ri1, ri2, ri3, ri4, ri5), 分别代表该装备对不同的属性值增幅。
当妞妞装备多件装备的时候,由于装备之前会互相影响, 对于每种属性值的增幅并不是所有装备该属性值之和, 而是该种属性值下所有装备中最大的属性值。而妞妞最终增加的战斗力为这5种属性值增幅之和。
妞妞一定要保卫牛家庄, 所以她希望她能提升尽可能多的战斗力, 请你帮帮她计算她最多能增加多少战斗力。
输入描述:
输入包括N+1行,
第一行包括两个正整数N和K(1 <= N <= 10000, 1 <= K <= N), 分别表示一共有的装备数量和妞妞需要选择的装备数量。
接下来的N行,每行5个整数ri1, ri2, ri3, ri4, ri5 (0 <= ri1, ri2, ri3, ri4, ri5 <= 10000)表示第i件装备的5种属性值增幅。
输出描述:
输出一个整数,表示妞妞最多能增加的战斗力。
输入例子1:
4 2
30 30 30 30 0
50 0 0 0 0
0 50 0 50 10
0 0 50 0 20
输出例子1:
170
例子说明1:
妞妞要从4件装备中选取2件, 如果妞妞选择第1件和第3件装备,那么增加的战斗力为30 + 50 + 30 + 50 + 10 = 170, 这是最大的方案。
这是我上周六做牛客网的Nowcoder Girl编程比赛时没有AC的一道题（第四题），加了比赛的QQ群，在里面得到了解题方法。
我们定义一个m数组，它是一个长32位的数组。每个下标可以看做一个5位二进制数，例如101002这样代表取一件武器的第1、3项属性的和，m[101002]n件兵器中单件兵器第1、3项属性和的最大值。
以k=2件兵器为例，那么5种属性中一部分来自第一件武器，另外的属性来自第二件武器。
如果k>=5是可以挑选5个单项最大值的武器，否则就按上面的方法进行组合。
好神奇有木有~
AC代码
//
// Created by Xue Li on 2017/12/23.
//
#include <iostream>
#include <vector>
using namespace std;
int n, k;
int result = 0;
void dfs(vector<int>& m, int p, int start, int flag, int value){
if (p == k){
if (value > result) {
result = value;
}
return;
}
for (int i = start; i < 32; i++){
if ((flag & i) == 0){
dfs(m, p+1, i+1, flag | i, value + m[i]);
}
}
}
int main() {
cin >> n >> k;
vector<int> r(5, 0);
vector<int> m(32, 0);
for (int i = 0; i < n; i++){
for (int j = 0; j < 5; j++)
cin >> r[j];
for (int j = 0; j < 32; j++){
int tmp = 0;
for (int k = 0; k < 5; k++){
if (((1 << k) & j) != 0)
tmp += r[k];
}
if (tmp > m[j])
m[j] = tmp;
}
}
if (k >= 5){
for (int j = 0; j < 5; j++){
result += m[1<<j];
}
cout << result;
return 0;
}
dfs(m, 0, 0, 0, 0);
cout << result;
return 0;
}
