题目链接:uva 11825
题意:
你是一个黑客,侵入了n台计算机(每台计算机有同样的n种服务),对每台计算机,你能够选择终止一项服务,则他与其相邻的这项服务都终止。你的目标是让很多其它的服务瘫痪(没有计算机有该项服务)。
思路:(见大白70页,我的方程与大白不同)
把n个集合P1、P2、Pn分成尽量多的组,使得每组中全部集合的并集等于全集,这里的集合Pi是计算机i及其相邻计算机的集合,用cover[i]表示若干Pi的集合S中全部集合的并集,dp[s]表示子集s最多能够分成多少组,则
假设cover[s]=all,那么dp[s]至少为1.
dp[s]=max(dp[s],dp[s0]+dp[s^s0]); (两个子集的和)
代码:
#include <cstdio> #include <cstring> #include <algorithm> #define N 16 using namespace std; int n, m, x, dp[1<<N], cover[1<<N], p[N]; int main () { int k = 0; while(scanf("%d",&n), n) { for(int i = 0; i < n; i++) { p[i] = 1<<i; scanf("%d",&m); for(int j = 0; j < m; j++) { scanf("%d",&x); p[i] |= 1<<x; } } 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]; } dp[0] = 0; int all = (1<<n)-1; for(int s = 1; s < (1<<n); s++) { if(cover[s]!=all) dp[s] = 0; else dp[s]=1; for(int s0 = s; s0; s0 = (s0-1)&s) // 枚举子集的技巧 s0为s除空集之外的全部子集 { dp[s] = max(dp[s], dp[s^s0]+dp[s0]); } } printf("Case %d: %d\n",++k, dp[all]); } return 0; } /* 3 2 1 2 2 0 2 2 0 1 5 2 0 1 2 0 2 2 0 1 1 4 1 3 4 2 1 2 3 0 2 3 3 0 1 3 2 1 2 */
uva 11825 Hackers' Crackdown (状压dp,子集枚举),布布扣,bubuko.com
uva 11825 Hackers' Crackdown (状压dp,子集枚举)
原文:http://www.cnblogs.com/hrhguanli/p/3837911.html