正文

uva 11825 Hackers' Crackdown （状压dp，子集枚举）

IP云
IP云V管理员/0 阅读
12/01
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：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&#39; Crackdown （状压dp，子集枚举）的更多相关文章
  1. UVA 11825 - Hackers&#39; Crackdown 状态压缩 dp 枚举子集

    UVA 11825 - Hackers' Crackdown 状态压缩 dp 枚举子集 ACM 题目地址:option=com_onlinejudge&Itemid=8&page=sh ...

  2. HDU6321 Dynamic Graph Matching【状压DP 子集枚举】

    HDU6321 Dynamic Graph Matching 题意: 给出\(N\)个点,一开始没有边,然后有\(M\)次操作,每次操作加一条无向边或者删一条已经存在的边,问每次操作后图中恰好匹配\( ...

  3. UVa 11825 Hackers' Crackdown (状压DP)

    题意:给定 n 个计算机的一个关系图,你可以停止每台计算机的一项服务,并且和该计算机相邻的计算机也会终止,问你最多能终止多少服务. 析:这个题意思就是说把 n 台计算机尽可能多的分成一些组,使得每组的 ...

  4. UVA - 1252 Twenty Questions （状压dp）

    状压dp,用s表示已经询问过的特征,a表示W具有的特征. 当满足条件的物体只有一个的时候就不用再猜测了.对于满足条件的物体个数可以预处理出来 转移的时候应该枚举询问的k,因为实际上要猜的物品是不确定的 ...

  5. [UVA11825]Hackers' Crackdown(状压dp)

    题解降智警告 吐槽降智警告 思路降智警告 代码降智警告 题目传送门 洛谷 果然水题做多了连半道难点的都能给咱干蒙... 水题做多了降智  --鲁迅 题目大意:见传送门 心路历程见末尾 正解(大概): ...

  6. UVA11825 黑客的攻击 Hackers' Crackdown 状压DP，二进制，子集枚举

    题目链接Click Here [题目描述] 假如你是一个黑客,侵入了一个有着\(n\)台计算机(编号为\(1.2.3....n\))的网络.一共有\(n\)种服务,每台计算机都运行着所有服务.对于每台 ...

  7. UOJ #348 州区划分 —— 状压DP+子集卷积

    题目:http://uoj.ac/problem/348 一开始可以 3^n 子集DP,枚举一种状态的最后一个集合是什么来转移: 设 \( f[s] \) 表示 \( s \) 集合内的点都划分好了, ...

  8. UVA 11825 Hackers’ Crackdown 状压DP枚举子集势

    Hackers’ Crackdown Miracle Corporations has a number of system services running in a distributed com ...

  9. UVa 1252 - Twenty Questions（状压DP）

    链接: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem& ...

随机推荐
  1. (@DBRef)spring-data-mongodb

    @DBRef用在哪些地方 已知的有 @DBRefprivate Shop product; @DBRefprivate List<Account> accounts;    如果不加@DB ...

  2. ajax调用webservice（二） 跨域。

    所需工具与项目结构同(一). service.asmx中代码如下: using System; using System.Collections.Generic; using System.Web; ...

  3. CSS 样式属性锦集

    ul#nav > Li 只有一个大于号,是指应用了#nav这个ID的下一级元素的儿子辈Li 元素定义的内容符合这个CSS代码定义的样式,但是孙子辈Li元素定义的内容就不符合这个CSS代码样式了, ...

  4. 武汉科技大学ACM ：1004: A+B for Input-Output Practice (IV)

    Problem Description Your task is to Calculate the sum of some integers. Input Input contains multipl ...

  5. scss组件定制的一些学习

    应组织上的要求,简化前端开发,提高工作效率,开始着手研究scss框架及组件化. 把一些长的像的弄在一起,就有了组件化. 但组件只用一部分需要的,就有了定制. 下面是参考一个button组件写出的一些简 ...

  6. Project: Individual Project - Word frequency program-11061160顾泽鹏

    一.预计用时: (1)明确要求:15min: (2)文件的遍历:1h: (3)Simple mode 词频统计:0.5h: (4)extend mode 词频统计:1h: (5)对单词词频排序输出:0 ...

  7. Unity中的各种寻找GameObject方法

    1.GameObject.Find():寻找Hierarchy面板中的activie 不为false的游戏对象: 路径如官方事例写法: public class ExampleClass : Mono ...

  8. c#使用UIA进行模拟点击操作

    之前,我写过一篇c#使用spy进行模拟操作的文章,有朋友在留言中提到了UIA进行操作,今天也使用UIA重新实现一次对vnc窗体的控制测试. 实现目标 在server框内填入192.168.2.200 ...

  9. ossim/zabbix/logstash

    http://dl528888.blog.51cto.com/2382721/1639579 http://307033.blog.51cto.com/297033/473666 http://lym ...

  10. AD14中如何定义PCB尺寸大小（不同于AD9和10）

    以前用的着软件基本都是停留在9和10,14用的少,虽然14增加了很多功能,但是也带来了不变,虽然可以打开各种其他格式的文件,但是有些地方的改动不容忽略,在一个完整的板子下来需要用到的每个地方的点也会有 ...

相关阅读

目录[+]