UVA 1508 - Equipment 狀態壓縮 枚舉子集 dfs

UVA 1508 - Equipment 狀態壓縮 枚舉子集 dfs

ACM

題目地址：UVA 1508 - Equipment--PDF

題意：
給出n個5元組，從中選出k組，使得這些組中5個位置，每個位置上最大數之和最大。

分析：
想了好久...最後還是參考了別人的題解...
不過思路很棒，值得學習。

由於n的范圍為1,10000，所以從n考慮是很難解出來的。
於是我們從5元組考慮。
每組5元組，最後可能被選擇作為和的一部分，就是[11111]，即[全部被選中做和]的子集，一共有31種情況。
我們只要預處理這31種情況可能得到的最大的和。然後dfs遍歷子集就行了。具體見代碼。

代碼：

/*
*  Author:      illuz 
*  File:        1508.cpp
*  Create Date: 2014-06-28 20:55:20
*  Descripton:   
*/

#include 
#include 
#include 
#include 
using namespace std;

const int N = 10010;
int n, t, k, ans;
int m[5], r[N][5], mmax[40];

int dfs(int S, int num) {	// find num different subset in S, return the max sum
	if (num == 0) {
		return 0;
	}

	int tmp = 0;
	for (int S0 = S; S0; S0 = (S0-1)&S) {
		tmp = max(tmp, mmax[S0] + dfs((S0^S), num - 1));
	}
	return tmp;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		memset(m, 0, sizeof(m));

		// input
		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 >= 5) {	// just the max

			int sum = 0;
			for (int i = 0; i < 5; i++) {
				sum += m[i];
			}
			printf("%d\n", sum);

		} else {

			memset(mmax, 0, sizeof(mmax));

			for (int i = 0; i < n; i++) {		// for every one
				for (int S = 0; S <= 31; S++) {	// every situation, 00000 to 11111
					int tmp = 0;
					for (int k = 0; k < 5; k++) {
						if (S&(1<