[Nowcoder315E] 勇敢的妞妞 (思维，状压，记忆化搜索)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://ac.nowcoder.com/acm/contest/315/E

美丽的牛家庄受到了外星人的侵略, 勇敢的妞妞要上战场抵御侵略。

在妞妞上战场前, 村长牛牛给了妞妞N件装备, 妞妞需要选择其中的K件,装备在身上提升自己的战斗力。每件装备有5种属性增幅值,对于第i件装备它的属性增幅值为(ri1, ri2, ri3, ri4, ri5), 分别代表该装备对不同的属性值增幅。

当妞妞装备多件装备的时候,由于装备之前会互相影响, 对于每种属性值的增幅并不是所有装备该属性值之和, 而是该种属性值下所有装备中最大的属性值。而妞妞最终增加的战斗力为这5种属性值增幅之和。

妞妞一定要保卫牛家庄, 所以她希望她能提升尽可能多的战斗力, 请你帮帮她计算她最多能增加多少战斗力。

首先能想到的是当$K\geq 5$时，只要在N件装备里选出5种属性中分别的最大值即可。

由于只有5种属性，我们可以关心每件装备对不同属性组合的贡献，于是可以状态压缩，比如我只关心第1、3属性的装备谁最大，那么这个状态就是$(10100)_2$，我们记录每种状态下都是哪个装备能提供最大幅度的增长，维护这个数组$hi$.

接下来希望尝试不同子状态的组合，比如$(10100)_2$和$(01001)_2$可以组合成$(11101)_2$，那么他们对答案的贡献就是$hi(10100_2)+hi(01001_2)$。所以我们直接先写个爆搜。

发现这个爆搜的状态重复了，于是记忆化一下就可以剪掉一部分搜索分支了。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 10100;
int n, k, ret;
int hi[1<<6];
int r[maxn][6];
int dp[6][1<<6];

int dfs(int cnt, int done, int start) {
  if(~dp[cnt][done]) return dp[cnt][done];
  if(cnt == k) return 0;
  int ret = 0;
  for(int i = start; i < (1 << 5); i++) {
    if((i & done)) continue;
    ret = max(ret, dfs(cnt+1, done|i, i+1) + hi[i]);
  }
  return dp[cnt][done] = ret;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&k)) {
    for(int i = 0; i < n; i++ ) {
      for(int j = 0; j < 5; j++) {
        scanf("%d", &r[i][j]);
      }
    }
    memset(dp, -1, sizeof dp);
    memset(hi, 0, sizeof hi);
    if(k > 5) k = 5;
    for(int st = 0; st < (1 << 5); st++) {
      for(int i = 0; i < n; i++) {
        int tmp = 0;
        for(int j = 0; j < 5; j++) {
          if(st & (1 << j)) tmp += r[i][j];
        }
        hi[st] = max(hi[st], tmp);
      }
    }
    printf("%d\n", dfs(0, 0, 0));
  }
  return 0;
}