当前位置: 代码迷 >> 综合 >> 例题29 UVa11825 Hackers' Crackdown(DP:子集)
  详细解决方案

例题29 UVa11825 Hackers' Crackdown(DP:子集)

热度:52   发布时间:2024-01-16 13:30:45.0

题意:

看白书二P67

要点:

这题还是有点难度的,思维上比较难想到,具体解析看白书吧。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1 << 20;
int s[N],p[N],cover[N],f[N];int main()
{int n;int i,kase=1;while (~scanf("%d", &n) && n){int m,x;for (i = 0; i < n; i++){scanf("%d", &m);p[i] = 1 << i;while (m--){scanf("%d", &x);p[i] |= (1 << x);}}for (int S = 0; S <= (1 << n); S++)//S表示不同pi的并集{cover[S] = 0;for (i = 0; i < n; i++)if (S&(1 << i))cover[S] |= p[i];//cover表示当前S的某个服务的并集}int all = (1 << n) - 1;f[0] = 0;for (int S = 1; S < (1 << n); S++){f[S] = 0;for (int S0 = S; S0; S0 = (S0 - 1)&S)if (cover[S0] == all)f[S] = max(f[S], f[S^S0] + 1);}printf("Case %d: %d\n", kase++, f[all]);}return 0;
}