UVa 11218 KTV

題意：
    總共有9個人(編號1~9)要分成3組唱歌，每組3個人，每個人只能唱一次。第一行N表示底下有N種組合，每種組合a,b,c,s，前三個是人員編號，s是該組合的分數。從N種中任選三種組合使得1~9號都能唱到歌，並且使得分數的和最高，輸出該分數，如果找不到組合滿足大家都能唱到歌則輸出-1。

想法：
    bitmask，(1<<9)-1表示所有人都唱的到歌的狀態，二進位來看就是(111111111)2，dp[i]=j表示在狀態i的情況下最高分數為j，因此dp[(1<<9)-1]就是所有人唱的到歌的最高分數。
    用dfs來枚舉不同組合，當人員沒有重複的時候才能將兩個狀態合併在一起，例如(000000111)2和(000111000)2這兩個狀態可以合併變成(000111111)2，並去更新dp[(000111111)2]的分數，不斷更新所有可能的合併來枚舉所有情況。

	#include <cstdio>
	#include <cstring>
	struct Combination{
	unsigned int bit;
	int score;
	};
	Combination C[100];
	int dp[1<<9];
	void dfs(int, unsigned int, int);
	bool CombineCheck(unsigned int, unsigned int);
	int main()
	{
	int N, a, b, c, s, Case = 1;
	while (scanf("%d", &N) && N) {
	// Input
	for (int i = 0; i < N; ++i) {
	scanf("%d %d %d %d", &a, &b, &c, &s);
	C[i].bit = (unsigned int)0 | (1<<(a-1)) | (1<<(b-1)) | (1<<(c-1));
	C[i].score = s;
	}
	// dfs for every possible combination
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < N; ++i)
	dfs(N, C[i].bit, C[i].score);
	// Output
	printf("Case %d: ", Case++);
	if (dp[(1<<9)-1] == 0) puts("-1");
	else printf("%d\n", dp[(1<<9)-1]);
	}
	}
	void dfs(int N, unsigned int bit, int score)
	{
	for (int i = 0; i < N; ++i) {
	if (CombineCheck(bit, C[i].bit)) {
	unsigned int combined_bit = bit | C[i].bit;
	if (dp[combined_bit] < score + C[i].score) {
	dp[combined_bit] = score + C[i].score;
	dfs(N, combined_bit, dp[combined_bit]);
	}
	}
	}
	}
	bool CombineCheck(unsigned int a, unsigned int b)
	{
	unsigned int c = a | b;
	int numA = 0, numB = 0, numC = 0;
	for (int i = 0; i < 9; ++i) {
	if (a & (1<<i)) ++numA;
	if (b & (1<<i)) ++numB;
	if (c & (1<<i)) ++numC;
	}
	return numA + numB == numC;
	}

view raw [UVa] 11218 KTV.cpp hosted with ❤ by GitHub