11825 - Hackers' Crackdown 状态压缩 dp 枚举子集

11825 - Hackers' Crackdown 状态压缩 dp 枚举子集

ACM

题目地址:11825 - Hackers' Crackdown

题意:
有一个由编号0~n-1的n台计算机组成的网络,一共有n种服务,每台计算机上都运行着全部服务,对于每台计算机,你可以选择停止一项服务,这个行为会导致与这台计算机和与他相连的其他计算机上的这项服务都停止(原来已经停止的继续保持停止状态)。求最多能使多少个服务瘫痪(即没有任何一台计算机在运行这项服务)。

分析:
题目说白了,就是:
把n个集合p[i],0分成尽量多组,使得每组中各个集合的并集为全集。
利用状态压缩,记录每个节点运行的服务。由于数据大小就16所以直接可以用int范围数字表示一个集合。
然后预处理下cover,处理16个节点组成的各个集合会带来的挺服务效果。
然后dp,如果cover[S0] == all (all全为1) 那么是S^S0 的部分也有可能终止服务 ,
dp[S] = max(dp[S], dp[S^S0]+1)。

参考了凌乱的心巨巨的题解,嘛,是为了了解枚举子集做的题目。

枚举子集的模板:

  1. // 对于集合S
  2. for (int S0 = S; S0; S0 = S&(S0 - 1)) // 枚举S0为子集
  3. ...

    原理:S&(S0 - 1) 实际上是把S中的0全部忽略,并不断减1的结果。

代码:

/* * Author: illuz * File: 11825.cpp * Create Date: 2014-06-27 20:43:48 * Descripton: sub set/ dp/ numeric */ #include #include #include using namespace std; const int N = 16; int n, m, t, mask[N], cover[1

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:hdu 2767 Proving Equivalences 强连通缩点
下一篇:bzoj 2109 & 2535 航空管制 题解
相关文章

DP25 子集和问题 Subset Sum Prob

uva 11825 Hackers' Crack

UVA 11205 The broken pedometer(

UVA 1508 - Equipment 状态压缩

ACM:回溯法,子集生成

(每日算法)LeetCode --- Subsets(子

HDU 4085 Peach Blossom Spring

C++中的运算符重载函数基础及其值返回

POJ 2923 Relocation 状态DP+01背包

hdu 4336 dp求期望(状态压缩)

图文推荐

11825 - Hackers' Crackdown 状态压缩 dp 枚举子集
ZOJ 3640 Help Me
11825 - Hackers' Crackdown 状态压缩 dp 枚举子集
CF 518C(Anya and
11825 - Hackers' Crackdown 状态压缩 dp 枚举子集
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-02 人气:6
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.056 (s). 10 q(s)