本文主要是介绍uva 11825 - Hackers' Crackdown(dp+子集枚举），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 11825 - Hackers' Crackdown
题目大意：黑客入侵了一个包含n台电脑的网络，每台网络上都运行了1~n，n中服务，现在给出每台电脑所直接连接的电脑。黑客可以对电脑安装一种病毒k（一台电脑只能安装一种），会导致与该台电脑直接相连的（包括本身）电脑无法提供k种服务，当网络中没有电脑可以提供k种服务时，则称该种服务瘫痪。求最多可以使几种服务瘫痪。
解题思路：dp+子集枚举，首先用n最大为16，完全可以用二进制储存，将每个电脑直接相连的电脑用二进制数组link保存。然后枚举所有集合的可能，将这种集合覆盖的范围同样用二进制储存在cover数组中，cover[i] = j（i表示集合选中的电脑，j表示覆盖到的电脑）。最后dp，用到枚举子集，假设集合s为i的一个子集，则（s-1）&i为i的下一个子集，直至s为0.
#include <stdio.h>
#include <string.h>
#include <algorithm>using namespace std;
const int N = 1<<17;int n, tmp, dp[N], cover[N], link[N];void init () {int m, k;memset(dp, 0, sizeof(dp));memset(cover, 0, sizeof(cover));memset(link, 0, sizeof(link));tmp = (1<<n);for (int i = 0; i < n; i++) {scanf("%d", &m);link[i] |= (1<<i);for (int j = 0; j < m; j++) {scanf("%d", &k);link[i] |= (1<<k);}} for (int i = 0; i < tmp; i++) {for (int j = 0; j < n; j++) if (i & (1<<j)) {cover[i] |= link[j];}}
}int solve () {for (int i = 0; i < tmp; i++) {for (int j = i; j; j = (j-1)&i) {if (cover[j] == tmp-1) {dp[i] = max(dp[i], dp[i^j]+1);}}}return dp[tmp-1];
}int main () {int cas = 1;while (scanf("%d", &n) == 1 && n) {init();printf("Case %d: %d\n", cas++, solve());}return 0;
}
这篇关于uva 11825 - Hackers' Crackdown(dp+子集枚举）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
