题意:N台电脑,现在有N种服务,现在你可以在每台电脑终止一项服务,他和他相邻的电脑都会被关闭,如果一项服务在所有电脑都没运行,该项服务成功被破坏,问最多能破坏几种服务。

分析:把n个集合分成尽量多组,使每组中的集合(为电脑i及相邻电脑的集合)的并集为全集,通过这个题学到了状态s的每位表示一个集合是否被并,dp[s]状态s是能破坏的最多服务,dp[s]=max(dp[s],dp[s^ss]+1)(ss是s的子集且表示的集合的并集是全集)。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
#define N 1<<17
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
int dp[N],c[N],cover[N],n;
int solve(){
int cas=(<<n)-;
for(int s=;s<=cas;++s){
cover[s]=;
for(int i=;i<n;++i)
if(s&(<<i))
cover[s]|=c[i];//把表示的集合并起来
}
dp[]=;
for(int s=;s<=cas;++s){
dp[s]=;
for(int i=s;i;i=((i-)&s))//枚举s的子集
if(cover[i]==cas)
dp[s]=max(dp[s],dp[s^i]+);
}
return dp[cas];
}
int main()
{
int num=;
while(~scanf("%d",&n)){
if(n==)break;
int a;
for(int i=;i<n;++i){
c[i]=(<<i);
scanf("%d",&a);
int x;
while(a--){
scanf("%d",&x);
c[i]|=(<<x);//相邻电脑组成的集合
}
}
printf("Case %d: %d\n",++num,solve());
}
return ;
}

最新文章

  1. listView当中有嵌套了有onClickListener的控件时ListView自身的onItemClick无响应的解决方案
  2. NHibernate 映射失败 is not mapped
  3. yum出现“No module named yum”错误解决方法
  4. AFNetworking 提示&quot;The resource could not be loaded because the App Transport Security policy requires the use of a secure connection&quot; 解决办法
  5. javascript 常用方法
  6. Android开发-API指南-&lt;category&gt;
  7. Java操作Wrod文档的工具类
  8. openstacks
  9. IOS UI篇—UILabel的文字顶部对齐
  10. Windows Live Writer针对CNBLOG的代码高亮插件
  11. 报错:loaded the &quot;&quot; nib but didn&#39;t get a UITableView
  12. win10 系统下获取系统版本号为6.2的问题(manifest如何写)
  13. AJAX跨域问题总结
  14. springboot使用RestHighLevelClient批量插入
  15. 洛谷P1880 石子合并(环形石子合并 区间DP)
  16. 基于mpvue搭建微信小程序
  17. solr的基础使用
  18. CentOS7 修改MAC地址
  19. varnish实践
  20. java 的nio与io对比

热门文章

  1. Java中的IO流系统详解
  2. 读书笔记汇总 --- 用Python写网络爬虫
  3. unity3d引擎程序员养成
  4. SDIBT 3237 Boring Counting( 划分树+二分枚举 )
  5. Delphi XE5 android toast
  6. What we learned in Seoul with AlphaGo
  7. [转载]ASP.NET MVC 3的分部视图
  8. 跨平台查询文件时间,如果超过7天,删除该文件(windows和linxu测试过)
  9. 【流媒體】live555—VS2008 下live555编译、使用及测试
  10. Servlet课程0426(十二)Servlet MV模式下用户登录及查看用户表中所有用户