UVA 1508 Equipment 题目链接 题意：给定n装备，每个装备对应5个分，现在选出k个装备，5个位置的分为每个装备最大的分，问选出最大的分和是多少 思路：5个分，那么对于每个装备，选到最大位置其实有2^5总情况，先预处理出来，然后在这个基础上，每次去枚举集
题目链接
题意：给定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;
}
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
399
收藏
