UVa 11825 (状压DP) Hackers' Crackdown
2024-08-25 14:40:53
这是我做状压DP的第一道题,状压里面都是用位运算来完成的,只要耐下心来弄明白每次位运算的含义,还是容易理解的。
题意:
有编号为0~n-1的n台服务器,每台都运行着n中服务,每台服务器还和若干台其他服务器相连。对于每台服务器,你可以选择停止该台以及与这台服务器相连的服务器的一项服务。如果一台服务器的所有服务都被停止,则这台服务器瘫痪。问最多能使多少台服务器瘫痪
转化为数学模型(题目是如何抽象成这种数学模型的也要好好想想):
把n个集合尽可能多的分成若干组,使得每组所有集合的并集为全集。这里集合Pi表示服务器i以及与其相邻服务器的集合
算法:
数组P[i]表示服务器i以及与其相邻服务器的集合的二进制表示
枚举所有集合可能的组合情况,一共有2n种,计算其并集保存在cover中
f[S]表示子集S最多可以分成多少组
状态转移方程:
枚举S的子集S0
f[S] = max{f[S], f[S - S0] + 1 | 这里S0是S子集而且cover[S0]为全集}
这里再说一下枚举S0用代码实现的技巧:
在二进制中S0的1的个数肯定比S要少,所以从数值大小上来看S0 < S
我们先令S0 = S - 1
那么 S & (S0 - 1)就是S的子集了
因为上面的表达式满足两个条件:
- S0 < S
- S0的1的个数比S要少
S ^ S0的含义:
S ^ S0代表以S为全集S0的补集,为什么用异或运算实现呢?自己动手模拟一下就清楚了,嘿嘿
好了,写到这里,这道题就分析的很透彻了。看来位运算还是蛮有意思的
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ( << ) + ;
int cover[maxn], p[], f[maxn]; int main(void)
{
#ifdef LOCAL
freopen("11825in.txt", "r", stdin);
#endif int n, kase = ;
while(scanf("%d", &n) == && n)
{
memset(f, , sizeof(f));
for(int i = ; i < n; ++i)
{
int m, x;
scanf("%d", &m);
p[i] = ( << i);
while(m--)
{
scanf("%d", &x);
p[i] |= ( << x);
}
} for(int i = ; i < ( << n); ++i)
{
cover[i] = ;
for(int j = ; j < n; ++j)
{
if(i & ( << j))
cover[i] |= p[j];
}
} f[] = ;
int all = ( << n) - ;
for(int s = ; s < ( << n); ++s)
{
f[s] = ;
for(int s0 = s; s0; s0 = (s0 - ) & s)
if(cover[s0] == all)
f[s] = max(f[s], f[s0 ^ s] + );
} printf("Case %d: %d\n", ++kase, f[all]);
}
return ;
}
代码君
最新文章
- 中文分词工具探析(一):ICTCLAS (NLPIR)
- redis和memcached的区别(总结)
- 项目中常用的linux命令
- .net学习之Session、Cookie、手写Ajax代码以及请求流程
- UNIX环境高级编程笔记之线程
- MecAnim
- ES2015 (ES6)
- Hibernate项目里配置环境时,jar包配置不当会对测试结果产生影响。
- [20190416]exclusive latch测试脚本.txt
- 快速搭建一个vue开发环境
- DirectX11 With Windows SDK--15 几何着色器初探
- impdp导入dmp数据实例
- MyEclipse Web项目部署失败:Deployment failure on Tomcat 7.x.Could not copy all resources to XXX.
- gulp + gulp-better-rollup + rollup 构建 ES6 开发环境
- PythonStudy——编程基础 Python Primary
- ELK日志收集分析平台 (Elasticsearch+Logstash+Kibana)使用说明
- 快速沃尔什变换与k进制FWT
- Logback中文文档(二):体系结构
- 转载:sql用逗号连接多张表对应哪个join?
- SQL Server 各版本安装包分享