题目

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2925

题意

n个节点,每个节点都有完全相同的n项服务。

每次可以选择一个节点,破坏该节点和相邻节点的某项服务。

问最多能完全破坏多少服务?

思路

如刘书,

直接枚举状态的子集

注意元素个数为k的集合有C^k_n个子集,那么枚举的时间复杂度为sum{c^k_n * 2^k} = 3^n,当n=16时,3^n=4e7,可以承受。

注意枚举子集可以通过substa = (substa - 1)&sta来做,子集的补集则为substa ^ sta。

感想

1. 一开始觉得枚举时间是2^2n,觉得不行,还是缺乏细致的计算

代码

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
typedef pair<int, int> MyPair;
const int MAXN = ;
const int MAXSTA = << ;
int edges[MAXN][MAXN];
int edgeCnt[MAXN];
int vis[MAXN];
int vis2[MAXSTA];
int dp[MAXSTA]; int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
int n;
for (int ti = ; scanf("%d", &n) == && n; ti++) {
for (int i = ; i < n; i++) {
scanf("%d", edgeCnt + i);
for (int j = ; j < edgeCnt[i]; j++) {
scanf("%d", edges[i] + j);
}
}
int maxsta = ( << n) - ;
for (int sta = ; sta <= maxsta; sta++) {
memset(vis, , sizeof vis);
for (int i = ; i < n; i++) {
if (sta & ( << i)) {
vis[i] = true;
for (int j = ; j < edgeCnt[i]; j++) {
vis[edges[i][j]] = true;
}
}
}
bool fl = true;
for (int i = ; i < n; i++) {
if (!vis[i]) {
fl = false;
}
}
if (fl) {
dp[sta] = ;
}
else {
dp[sta] = ;
} }
for (int sta = ; sta <= maxsta; sta++) {
for (int subSta = sta; subSta != ; subSta = (subSta - ) & sta) {
dp[sta] = max(dp[sta], dp[sta ^ subSta] + dp[subSta]);
} }
printf("Case %d: %d\n", ti, dp[maxsta]);
} return ;
}

最新文章

  1. 安卓工具箱:color of Style
  2. Java编程里类的继承
  3. iOS 设置页面的代码编写
  4. 黄聪:wordpress如何获取当前页面的URL
  5. 邻结矩阵的建立和 BFS,DFS;;
  6. codeforces #310 div1 C
  7. SQL Server 2008连接字符串写法大全(摘自网络)
  8. 关于$GLOBALS[&#39;ecs&#39;]-&gt;table()的问题?
  9. knockoutjs简单使用
  10. 关于Unity中如何代码动态修改天空盒
  11. 光环国际联合阿里云推出“AI智客计划”
  12. 2015/12/24:嵌入式C语言的位操作随笔
  13. git HEAD detached from origin 问题的解决
  14. redis--解析字符串
  15. SpringBoot2.0整合mybatis、shiro、redis实现基于数据库权限管理系统
  16. java中Integer和int的区别(转)
  17. Centos + Maven + Jenkins
  18. async(await)知识点
  19. RALL资源获取初始化,删除器
  20. momenta

热门文章

  1. 学习笔记46—如何使Word和EndNote关联
  2. windows 网卡配置的设置命令
  3. ERROR org.redisson.client.handler.CommandDecoder - Unable to decode data. channel
  4. org.springframework.web.multipart.MultipartException: Failed to parse multipart servlet request; nested exception is java.io.IOException: The temporary upload location [/tmp/tomcat.1428942566812653608
  5. LeetCode--004--寻找两个有序数组的中位数(java)
  6. oracle 查看被锁表 及解除锁定
  7. js,vue.js一些方法的总结
  8. Fiddler抓取https数据包
  9. php url处理
  10. selenium 定时任务