Arrange the Bulls（状压dp)

本文主要是介绍Arrange the Bulls（状压dp)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Arrange the Bulls（状压dp)

题目大意：一些牛喜欢一些地方（每头牛都有一些喜欢的地方），现在要把这些地方分配给牛，每头牛都应该分到一个地方，问有多少种分配的方法

此题拥有着状压dp的鲜明特征，N和M只有20（看见这种数据的时候往状压dp上想一想），枚举每一种状态，判断合理性。像这种两种东西匹配的状压dp的题都基本是这种套路。

AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=20;
int dp[1<<maxn],pw[maxn+2][maxn+2];//前面存储被选走的地方是哪几个，后面是牛喜欢的地方
int N,M;
int dfs(int st,int pos)//现在是什么状态，现在这头牛是哪头
{
	if(pos==N)return 1;//到底了，方法为1
	if(~dp[st])return dp[st];//初始化为-1,判断条件就是这个
	int ans=0;
	for(int i=0;i<M;i++)
		if((st&(1<<i))==0&&pw[pos][i])
			ans+=dfs(st|(1<<i),pos+1);
	return dp[st]=ans;
}
int main(void)
{
	memset(dp,-1,sizeof(dp));//初始化为负一是因为存在某种情况方法数为0的情况
	scanf("%d %d",&N,&M);
	for(int i=0;i<N;i++)
	{
		int x;scanf("%d",&x);
		for(int j=0;j<x;j++)
		{
			int y;scanf("%d",&y);
			y--;//因为这里的地方是从1开始的，而这里我用二进制的1<<0表示第一位，所以要减一
			pw[i][y]=1;
		}
	}
	cout<<dfs(0,0)<<endl;
	return 0;
}

啊啊啊！！！要与网路流的匹配区分开来，两个的数据量就很不同好吧。

这篇关于Arrange the Bulls（状压dp)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！