Uva 11825 - Hackers’ Crackdown 状态压缩DP

Uva 11825 - Hackers’ Crackdown 状态压缩DP

题意:

有N个电脑..每个电脑都运行着N个相同的进程..现在来黑这些电脑..对于每个电脑..可以黑掉它的一个进程..这么做..和它相邻电脑的这个进程也会崩溃..如果一个进程 没有一台电脑运行了..就那么这个进程就挂了..问最多能挂掉多少个进程.

题解:

也不算题解了..自己没想出来..参考了别人的思想....只是说下自己的理解..

将每个点i以及其相邻的点看成集合..一共N个集合...这N个集合..对于每一个集合..只要黑i的某个进程..相邻的这个进程自然崩溃..也就是说.对于每个集合..必定可以在这个集合内把一个进程崩溃..而对于整个系统..一个进程要挂掉...就必定需要若干个集合的并..点数=N...问题转换..求最多的不相交的集合并..使得每一个集合并点数=N..并且集合并的个数最多...

首先把每个电脑相邻(包括)自己的情况用二进制表示出来..再将所有电脑组合的情况包括的电脑情况用二进制表示出来...这里很直接..主要是dp的状态转移..

dp[i] = max ( dp [i^k]+1 )

其中i表示的集合并必须覆盖到所有N个点..k是i的子集..i^k就是i对于k的补集..保证两个集合不相交..因为对于i来说只能多让一个进程挂..所以+1

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 17using namespace std; int n,A[MAXN],S[1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。