[BOJ 8903] 장비

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

8903번: 장비

Tag : case work

 

문제요약

장비마다 5개의 능력치가 있는데 장비를 여러개 골랐을 때 각각의 능력치는 고른 장비들에서 최대 하나로만 결정된다.

고를 수 있는 장비의 개수가 주어졌을 때 능력치 합의 최대를 구하라.

 

풀이

5개 이상 고를 수 있다면 각각의 능력치가 최대인 것을 하나씩 골라오면 된다.

그게 아니라면 \(O(2^{10} \times N)\) 비트마스킹 dp를 돌리면된다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
template<typename T>
struct FASTIO {
    char *p,O[2000000],*d;
    void set() {
        struct stat st;fstat(0, &st);d=O;
        p=(char*)mmap(0,st.st_size,1,1,0,0);
    }
    ~FASTIO() {
        write(1,O,d-O);
    }
    inline T get() {
        T x=0;bool e;p+=e=*p=='-';
        for(char c=*p++;c&16;x=10*x+(c&15),c=*p++);
        return e?-x:x;
    }
    inline void put(int x) {
        if(x<0) *d++='-', x=-x;
        char t[16],*q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=10;
    }
};

FASTIO<int> IO;

void solve() {
    int n = IO.get(), k = IO.get();
    vector<vector<int>> v(n);
    for(int i=0; i<n; i++) {
        v[i].resize(5);
        for(auto &j : v[i]) j = IO.get();
    }
    if(k >= 5) {
        int mx[5] = {0, 0, 0, 0, 0};
        for(int i=0; i<n; i++) {
            for(int j=0; j<5; j++) mx[j] = max(mx[j], v[i][j]);
        }
        IO.put(accumulate(mx, mx + 5, 0));
        return;
    }
    vector<vector<int>> dp(32, vector<int>(6));
    for(int i=0; i<n; i++) {
        vector<int> t(32);
        for(int j=0; j<32; j++) {
            for(int p=0; p<5; p++) if(j & (1 << p)) t[j] += v[i][p];
        }
        for(int cnt=1; cnt<=5; cnt++) {
            for(int j=0; j<32; j++) {
                for(int p=31-j; p>=0; p=(p-1)&(31-j)) {
                    dp[j | p][cnt] = max(dp[j | p][cnt], dp[p][cnt - 1] + t[j]);
                    if(p == 0) break;
                }
            }
        }
    }
    int ans = 0;
    for(int i=0; i<32; i++) ans = max(ans, dp[i][k]);
    IO.put(ans);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);

    IO.set();
    int TC = IO.get();
    while(TC--) {
        solve();
    }
}