POJ 2441 Arrange the Bulls 题解 《挑战程序设计竞赛》

POJ 2441 Arrange the Bulls

公牛队：农夫约翰有N支公牛队，分别独占M个球场中的若干个，求分配方案的个数？

3.4熟练掌握动态规划

状态压缩DP

白天写代码混饭，晚上写代码寻欢。

基本上是个带记忆的枚举，难点在对集合状态的枚举上。我第一次是这么干的：

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 20
#define MAX_M 20

vector<int> dp[2];	        // dp[now]表示满足了i的情况下剩下场地构成的集合S
vector<int> barn[MAX_N];	// 每个球队喜欢的球场

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		int P;
		cin >> P;
		barn[i].reserve(P);
		for (int j = 0; j < P; ++j)
		{
			int b;
			cin >> b; --b;
			barn[i].push_back(b);
		}
	}
	int S = (1 << M) - 1;
	for (int i = 0; i < barn[0].size(); ++i)
	{
		dp[0].push_back(S & ~(1 << barn[0][i]));
	}
	for (int i = 1; i < N; ++i)
	{
		int pre = (i - 1) & 1;
		int now = i & 1;
		dp[now].clear();
		for (int j = 0; j < barn[i].size(); ++j)
		{
			for (int k = 0; k < dp[pre].size(); ++k)
			{
				if (dp[pre][k] >> barn[i][j] & 1)
				{
					dp[now].push_back(dp[pre][k] & ~(1 << barn[i][j]));
				}
			}
		}
	}

	cout << dp[(N - 1) & 1].size() << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

结果MLE了，而且这里肯定不能用vector的，最后vector里面都是相同的S，估计应该用map记录S和出现的次数，可以省点内存。这里如果会枚举子集的话就相当省了：

基本枚举：

枚举子集：

定义 dp[S] := 当场地集合为S时，每个球队都不冲突的情况种数。

那么 dp[1 << (第一个球队喜欢的场地编号)] = 1

递推方法是，从第i个球队开始，枚举集合{0, 1, … , M – 1}的大小为i的子集，也就是分配了i个场地，满足了i个球队，如果球队i喜欢场地j并且j不在集合S中，那么dp[S ∪ j] += dp[S]。

#include <iostream>
#include <bitset>
using namespace std;
#define MAX_N 20
#define MAX_M 20

int dp[1 << MAX_M];	        // dp[S]表示已分配场地构成的集合S时的情况种数
bool like[MAX_N][MAX_M];	// like[i][j]表示球队i喜欢场地j

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		int P; cin >> P;
		for (int j = 0; j < P; ++j)
		{
			int b;
			cin >> b; --b;
			like[i][b] = true;
		}
	}
	for (int i = 0; i < M; ++i)
	{
		if (like[0][i])
		{
			dp[1 << i] = 1;	// 将i场地分配给0号球队
		}
	}
	for (int i = 1; i < N; ++i)
	{
		for (int comb = (1 << i) - 1, x, y; comb < (1 << M); x = comb & -comb, y = comb + x, comb = ((comb & ~y) / x >> 1) | y)
		{
			// comb表示集合{0, 1, ... , M - 1}的大小为i的子集，也就是分配了i个场地，满足了i个球队
			if (dp[comb])
			{
				for (int j = 0; j < M; ++j)
				{
					if (like[i][j] && !((comb >> j) & 1))
					{
						// i需要j并且j没有被分配，此时将j分配掉
						dp[comb | (1 << j)] += dp[comb];
					}
				}
			}
		}
	}

	int result = 0;
	for (int bit = 0; bit < (1 << M); ++bit)
	{
		if (bitset<32>(bit).count() == N)
		{
			result += dp[bit];
		}
	}
	cout << result << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2441 Arrange the Bulls 题解 《挑战程序设计竞赛》