8903번: 장비

https://www.acmicpc.net/problem/8903


$O(tn)$

최적해가 주어졌을 때, 최적해를 이루는 각 능력치의 값은 min(k,5)개 이하의 장비에서 (1개 혹은 여러)능력치를 선택해서 그대로 가져왔다고 할 수 있다.
선택되는 능력의 조합 31가지에 대해 능력치의 최대 합을 구해놓고
이들 조합 중 선택한 능력이 겹치지 않도록 min(k,5)개를 선택해서 최대 합을 찾는다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, n, c, m[32], a[5];
int f(int h, int l) {
    if (!l) return 0;
    int rt = 0;
    for (int i = 1; i < 32; i++) if (!(h&i)) rt = max(rt, f(h | i, l - 1) + m[i]);
    return rt;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &n, &c);
        fill(&m[0], &m[32], 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 5; j++) scanf("%d", a + j);
            for (int j = 1; j < 32; j++) {
                int s = 0;
                for (int k = 0; k < 5; k++) if (1 << k&j) s += a[k];
                if (m[j] < s) m[j] = s;
            }
        }
        printf("%d\n", f(0, min(c, 5)));
    }
    return 0;
}