首页 > 代码库 > POJ 2441 Arrange the Bulls（状压DP）
POJ 2441 Arrange the Bulls（状压DP）
【题目链接】 http://poj.org/problem?id=2441
【题目大意】
每个人有过个喜欢的篮球场地，但是一个场地只能给一个人，
问所有人都有自己喜欢的场地的方案数。
【题解】
状态S表示已经用了那些场地，顺序递推每个人满足需求的情况即可。
【代码】
#include <cstdio>#include <cstring>using namespace std;const int N=25;int n,m,u,x,dp[2][1<<20],a[N][N];int main(){ while(~scanf("%d%d",&n,&m)){ memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=n;i++){ scanf("%d",&u); while(u--)scanf("%d",&x),a[i][x]=1; } for(int i=1;i<=n;i++){ for(int j=0;j<(1<<m);j++)if(dp[1-i&1][j]){ for(int k=1;k<=m;k++){ if(a[i][k]&&j!=(j|1<<(k-1)))dp[i&1][j|1<<(k-1)]+=dp[1-i&1][j]; } }memset(dp[1-i&1],0,sizeof(dp[1-i&1])); }int ans=0; for(int i=1;i<(1<<m);i++)ans+=dp[n&1][i]; printf("%d\n",ans); }return 0;}POJ 2441 Arrange the Bulls（状压DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。