题目链接: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;
}
分享到:
相关推荐
the-database-hackers-handbook
Addison Wesley - Hackers Delight__ 2002
in-hackers-mind-源码.rar
11-how-hackers-learn-and-why-you-want-this-in-your-school
how-hackers-learn-and-why-you-want-this-in-your-school.pdf
最佳的75个安全工具 在2000年的5、6月间,nmap-hackers邮件列表中发起了最佳安全工具的评选活动,活动取得了成功,最终由1200名Nmap用户评选出了50个最佳安全工具,评选结果发布在insecure.org网站,得到了网友们的...
Deep learning is a form of machine learning that enables computers to learn from experience and understand the world in terms of a hierarchy of concepts. Because the computer gathers knowledge from ...
In Hacker’s Delight, Second Edition, Hank Warren once again compiles an irresistible collection of programming hacks: timesaving techniques, algorithms, and tricks that help programmers build more ...
twilio-bearcat-hackers
链接唤醒ROM Hack工具箱该工具旨在用于基于Links Awakening DX创建...安装LADX-Hackers-Toolbox使用进行转换和从安装python3.9(或更高版本),确保选中“将python添加到环境变量”以使您的生活更轻松。 从安装Tiled
nuxt-hackers-新闻 构建设置 # install dependencies $ npm install # serve with hot reload at localhost:3000 $ npm run dev # build for production and launch server $ npm run build $ npm run start # ...
Honeypots - Tracking Hackers.rar
智能关闭危险端口(bat文件) @echo off gpupdate >nul rem For Client only ipseccmd -w REG -p "HFUT_SECU" -o -x >nul ipseccmd -w REG -p "HFUT_SECU" -x >nul rem ipseccmd -w REG -p "HFUT_SECU" -r "Block ...
卡姆·哈克斯(Cam-Hackers) 哈克相机 执行方式: apt-get安装python3 apt-get安装git git clone pip3安装请求 pip3安装colorama cd Cam-Hackers python3 cam-hackers.py CAM-HACKERS CAM-HACKERS 贝宝...
McGraw.Hill.Gray.Hat.Hacking.The.Ethical.Hackers.Handbook.3rd.Edition.Jan.2011 pdf http://www.amazon.com/Gray-Hacking-Ethical-Hackers-Handbook/dp/0071742557/ref=sr_1_9?ie=UTF8&qid=1315966016&sr=8-9
Python 黑客研讨会 环境 Python 混帐 数据库 虚拟环境 系统参数 系统,操作系统库 地图、lambda、列表合成、字典合成、生成器示例:词表阅读器 子流程示例:nmap 处理程序 xml库示例:xml 解析 ...
大纲近年来,出现了一群人,他们有的人是科技公司里的工程师;有的人是程式自由工作者;有些人甚至是顶尖电脑黑客。在他们之间的共同点是,他们都拥有程式专业以及对改造社会的热情,并运用自身能力帮助人们。...
hackers-grep-hackers-grep 作为实用程序, 专注搜索 PE 可执行文件的指定字符串, 包含 输入/输出/调试符号
java源码 hacker
网络安全:黑客的思想 讲座幻灯片,注释,代码和参考。 主要议题 介绍 必需品 软件安全性 网络安全 Web应用安全 野生动物