UVA1508《Equipment》

三月 23, 2019 2280

ProjectDP - 33

状态压缩 + DFS

题面

PDF

解题思路

首先是这个玄学的数据范围（每个组只有5个元素）
很容易让人想到状压

首先把 k >= 5 的情况特判一下
可以选择超过5个组
那么显然选择最大的就行了

对于每一个组，枚举它的每一种状态
对于这个状态，统计一下选择这个状态的总和（被选择了的数的和），与所有组里这个状态的总和取个 max

这样我们就获得了每一种状态总和的最大值
对它进行一遍 DFS

这里说一个位运算技巧
枚举子集

1
for (int s0 = s; s0; s0 = s & (s0 - 1));

s0 即为 s 的某一个子集

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//
//  33.cpp
//  ProjectDP
//
//  Created by HandwerSTD on 2019/3/9.
//  Copyright © 2019 Handwer STD. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <cstdio>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 10000 + 10 ;

int qwq[5 + 5], grps[MAXN][5 + 5], dp[(1 << 5) - 1 + 10] ;
int n, k;

int Search(int s, int sum) {
    if (sum == 0) return 0;
    int tmp = 0 ;
    for (int s0 = s; s0; s0 = s & (s0 - 1))
        tmp = std::max(tmp, dp[s0] + Search ((s0 ^ s), sum - 1));
    return tmp;
}

int main() {
    IMPROVE_IO();
    int T = 0;
    cin >> T;
    while (T --> 0) {
        memset(qwq, 0, sizeof qwq);
        cin >> n >> k;
        for (int i = 1 ; i <= n; ++i)
            for (int j = 0; j < 5; ++j){
                cin >> grps[i][j];
                qwq[j] = std::max(qwq[j], grps[i][j]) ;
            }
        if (k >= 5) {
            int ans = 0;
            for (int i = 0 ; i < 5 ; ++i) ans += qwq[i] ;
            cout << ans << endl;
        } else {
            memset(dp, 0, sizeof (dp)) ;
            for (int i = 1; i <= n; ++i) {
                for (int stat = 0; stat <= (1 << 5) - 1; ++stat) {
                    int tmp = 0;
                    for (int sel = 0; sel < 5; ++sel) {
                        if (stat & (1 << sel)) tmp += grps[i][sel];
                    }
                    dp[stat] = std::max(dp[stat], tmp);
                }
            }
            cout << Search((1 << 5) - 1, k) << endl;
        }
    }
    return 0 ;
}