UVA 1508 Equipment(技巧枚举)

本文主要是介绍UVA 1508 Equipment(技巧枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 1508 Equipment

题目链接

题意：给定n装备，每个装备对应5个分值，现在选出k个装备，5个位置的分值为每个装备最大的分值，问选出最大的分值和是多少

思路：5个分值，那么对于每个装备，选到最大值位置其实有2^5总情况，先预处理出来，然后在这个基础上，每次去枚举集合即可，最多只要枚举5个集合（因为如果k > 5的话，其实答案就是选出5个分值对应最大的5个装备，其余随便选即可)

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int INF = 0x3f3f3f3f;
const int N = 5;
int t, n, k, a[N], s[(1<<N) + 5];void build() {for (int i = 0; i < (1<<5); i++) {int sum = 0;for (int j = 0; j < 5; j++) {if (i&(1<<j))sum += a[j];}s[i] = max(s[i], sum);}
}int dfs(int st, int d) {if (d == k) {if (st != 0) return -INF;return 0;}int ans = 0;for (int i = st; i; i = (i - 1)&st)ans = max(ans, dfs(st^i, d + 1) + s[i]);return ans;
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d", &n, &k);k = min(k, 5);memset(s, 0, sizeof(s));for (int i = 0; i < n; i++) {for (int j = 0; j < 5; j++)scanf("%d", &a[j]);build();}printf("%d\n", dfs((1<<5) - 1, 0));}return 0;
}

这篇关于UVA 1508 Equipment(技巧枚举)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---