admin管理员组

文章数量:1566220

题目大意：给出n个5元组，要求从中选取k个，要求5个位置上的数的最大值的和尽量大。

解题思路：对于每个元组，有25−1种选取方法，那么处理出这些选取方法中的最大值即可，然后暴力枚举。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int m[5], maxn[35];

int DFS(int S, int cnt) {
	if (cnt == 0)
		return 0;

	int temp = 0;
	for (int St = S; St; St = (St-1) & S)
		temp = max(temp, maxn[St] + DFS(St ^ S, cnt - 1));

	return temp;
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, k, R[10010][5];
		memset(m, 0, sizeof(m));
		memset(maxn, 0, sizeof(maxn));

		scanf("%d%d", &n, &k);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < 5; j++) {
				scanf("%d", &R[i][j]);
				m[j] = max(m[j], R[i][j]);
			}

		if (k > 4) {
			printf("%d\n", m[0] + m[1] + m[2] + m[3] + m[4]);
			continue;
		}

		for (int i = 0; i < n; i++)
			for (int S = 0; S < 32; S++) {
				int temp = 0;
				for (int j = 0; j < 5; j++)
					if (S & (1<<j))
						temp += R[i][j];
				maxn[S] = max(maxn[S], temp);
			}
		printf("%d\n", DFS(31, k));
	}
	return 0;
}


本文标签： 子集暴力uvaequipment

版权声明：本文标题：uva 1508 - Equipment(暴力+枚举子集) 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1726267063a1063356.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。