UVa 11825 Hackers’ Crackdown / 状态压缩DP

本文主要是介绍UVa 11825 Hackers’ Crackdown / 状态压缩DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码就是书上的 这题太神了 太好了

直接看书吧孩子 书上讲的蛮好的

2进制枚举子集还是很巧妙的

a[i]表示的树中1的地方表示相连 所有1组成一个集合

cover[i]表示a[i]的组合 比如i = 6 就是 110 就是a[1] a[2]2个集合的并集

dp[i]表示集合i做多终止几项服务

for(int s0 = s; s0; s0 = (s0-1)&s)

s0 枚举了s的子集 可以自己比划一下

如果cover[s0] == all (all全为1)  那么是s^s0 的部分也有可能终止服务 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1<<20];
int cover[1<<20];
int a[1<<20];
int main()
{int cas = 1;int n, i, j;while(scanf("%d", &n) && n){int m, x;for(i = 0; i < n; i++){scanf("%d", &m);a[i] = 1 << i;while(m--){scanf("%d", &x);a[i] |= (1<<x);}}for(int s = 0; s < (1<<n); s++){cover[s] = 0;for(i = 0; i < n; i++){if(s & (1<<i))cover[s] |= a[i];}}dp[0] = 0;int all = (1<<n) - 1;for(int s = 1; s < (1<<n); s++){dp[s] = 0;for(int s0 = s; s0; s0 = (s0-1)&s){if(cover[s0] == all)dp[s] = max(dp[s], dp[s^s0]+1);}}printf("Case %d: %d\n", cas++, dp[all]);}return 0;
}

 

这篇关于UVa 11825 Hackers’ Crackdown / 状态压缩DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---