[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;
}