UVa 11825 - Hackers' Crackdown DP, 枚举子集substa = (substa - 1)&sta 难度: 2
2024-10-15 05:57:34
题目
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 ;
}
最新文章
- 安卓工具箱:color of Style
- Java编程里类的继承
- iOS 设置页面的代码编写
- 黄聪:wordpress如何获取当前页面的URL
- 邻结矩阵的建立和 BFS,DFS;;
- codeforces #310 div1 C
- SQL Server 2008连接字符串写法大全(摘自网络)
- 关于$GLOBALS[&#39;ecs&#39;]->;table()的问题?
- knockoutjs简单使用
- 关于Unity中如何代码动态修改天空盒
- 光环国际联合阿里云推出“AI智客计划”
- 2015/12/24:嵌入式C语言的位操作随笔
- git HEAD detached from origin 问题的解决
- redis--解析字符串
- SpringBoot2.0整合mybatis、shiro、redis实现基于数据库权限管理系统
- java中Integer和int的区别(转)
- Centos + Maven + Jenkins
- async(await)知识点
- RALL资源获取初始化,删除器
- momenta
热门文章
- 学习笔记46—如何使Word和EndNote关联
- windows 网卡配置的设置命令
- ERROR org.redisson.client.handler.CommandDecoder - Unable to decode data. channel
- org.springframework.web.multipart.MultipartException: Failed to parse multipart servlet request; nested exception is java.io.IOException: The temporary upload location [/tmp/tomcat.1428942566812653608
- LeetCode--004--寻找两个有序数组的中位数(java)
- oracle 查看被锁表 及解除锁定
- js,vue.js一些方法的总结
- Fiddler抓取https数据包
- php url处理
- selenium 定时任务