题目描述

美丽的牛家庄受到了外星人的侵略, 勇敢的妞妞要上战场抵御侵略。
在妞妞上战场前, 村长牛牛给了妞妞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位二进制数，例如10100₂这样代表取一件武器的第1、3项属性的和，m[10100₂]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;
}