首页 > 代码库 > UVA11825 Hackers' Crackdown
UVA11825 Hackers' Crackdown
题解:
第一个状压dp题.所以写仔细些
题目转化为:
有n个集合进行分组,求最多满足条件的分组数
状态是:n个集合,每个集合选可或不选。共1<<n种情况
根据二进制,可以由前向后递推 f[s]=max(f[s-s0])+1, s0是s的子集,cover[s0]等于全集
子集枚举:
for (int x = S; x; x = (x-1)&S)
解释
http://www.cnblogs.com/jffifa/archive/2012/01/16/2323999.html
(x-1)&s把s中的0全部忽略,并不断减1的结果
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1<<17; int n,m,x,all,Case=1; int cover[maxn],f[maxn],p[17]; int main() { while(~scanf("%d",&n)&&n) { for(int i=0;i<n;i++) { p[i]=1<<i; scanf("%d",&m); while(m--) { scanf("%d",&x); p[i]|=(1<<x);//将每个点以及相邻的点的集合用二进制表示,一共有n个点,所以有n个集合 } } all=(1<<n)-1; for(int s=0;s<(1<<n);s++) { cover[s]=0; for(int i=0;i<n;i++) { if(s&(1<<i)) cover[s]|=p[i];//s表示选取的那几个集合的二进制和,cover[s]表示选取这些集合覆盖了多少点,二进制表示 } } for(int s=0;s<(1<<n);s++) { f[s]=0; for(int s0=s;s0;s0=(s0-1)&s)//s0为s的子集 { if(cover[s0]==all) f[s]=max(f[s],f[s^s0]+1); } } printf("Case %d: %d\n",Case++,f[all]); } return 0; }
UVA11825 Hackers' Crackdown
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。