[Technical Specification] 0<T<=100 8<n<=16 2<m<=5 0<k<=100 0<初始恐慌值<=5 每个州至少有三个国家 每次外星人进攻一定发生在不同州的三个国家
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iterator>
#include<stack>
using namespace std;
const int INF=1e9+;
const double eps=1e-;
const int maxn=;
int N,M,K;
vector<int> G[maxn];
int bel[maxn],val[maxn],ans;
struct Atk
{
int x,y,z;
Atk(int x=,int y=,int z=):x(x),y(y),z(z){}
}atk[];
bool work(int a,int y)
{
for(int i=;i<G[a].size();i++)
{
int c=G[a][i];
if(c==y) val[c]+=;
else val[c]+=;
if(val[c]>) return false;
}
return true;
}
void dfs(int step)
{
ans=max(ans,step);
if(step>=K) return;
int B[maxn];
for(int i=;i<N;i++) B[i]=val[i];
Atk& t=atk[step];
int x=t.x,y=t.y,z=t.z;
val[x]-=;
if(val[x]<) val[x]=;
if(work(bel[y],y)&&work(bel[z],z)) dfs(step+);
for(int i=;i<N;i++) val[i]=B[i];
val[y]-=;
if(val[y]<) val[y]=;
if(work(bel[x],x)&&work(bel[z],z)) dfs(step+);
for(int i=;i<N;i++) val[i]=B[i];
val[z]-=;
if(val[z]<) val[z]=;
if(work(bel[x],x)&&work(bel[y],y)) dfs(step+);
for(int i=;i<N;i++) val[i]=B[i];
return;
}
int main()
{
int T,Case=;
scanf("%d",&T);
while(T--)
{
for(int i=;i<maxn;i++) G[i].clear();
scanf("%d%d%d",&N,&M,&K);
int x,y,z;
for(int i=;i<N;i++)
{
scanf("%d",&x);
bel[i]=x;
G[x].push_back(i);
}
for(int i=;i<N;i++) scanf("%d",&val[i]);
for(int i=;i<K;i++)
{
scanf("%d%d%d",&x,&y,&z);
atk[i]=Atk(x,y,z);
}
ans=;
dfs();
printf("Case #%d: %d\n",++Case,ans);
}
return ;
}
hdu4536-XCOM Enemy Unknown(爆搜)的更多相关文章
-
HDU4536 XCOM Enemy Unknown(dfs)
题目链接. 分析: 用dfs枚举每一波攻击的三个国家. 很暴力,但没想到0ms. #include <iostream> #include <cstdio> #include ...
-
【BZOJ-1853&;2393】幸运数字&;Cirno的完美算数教室 容斥原理 + 爆搜 + 剪枝
1853: [Scoi2010]幸运数字 Time Limit: 2 Sec Memory Limit: 64 MBSubmit: 1817 Solved: 665[Submit][Status] ...
-
POJ 1166	The Clocks (爆搜 || 高斯消元)
题目链接 题意: 输入提供9个钟表的位置(钟表的位置只能是0点.3点.6点.9点,分别用0.1.2.3)表示.而题目又提供了9的步骤表示可以用来调正钟的位置,例如1 ABDE表示此步可以在第一.二.四 ...
-
【 POJ - 1204 Word Puzzles】(Trie+爆搜|AC自动机)
Word Puzzles Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 10782 Accepted: 4076 Special ...
-
hdu5323 Solve this interesting problem(爆搜)
转载请注明出处: http://www.cnblogs.com/fraud/ ——by fraud Solve this interesting problem Time Limit ...
-
poj1077 Eight【爆搜+Hash(脸题-_-b)】
转载请注明出处,谢谢:http://www.cnblogs.com/KirisameMarisa/p/4298840.html ---by 墨染之樱花 题目链接:http://poj.org/pr ...
-
[NOIP2015] 斗地主 大爆搜
考试的时候想了半天,实在是想不到解决的办法,感觉只能暴力..然后暴力也懒得打了,小数据模拟骗30分hhh 然而正解真的是暴力..大爆搜.. 然后我的内心拒绝改这道题(TAT) 不过在wcx大佬的帮助下 ...
-
BZOJ 1207: [HNOI2004]打鼹鼠【妥妥的n^2爆搜,dp】
1207: [HNOI2004]打鼹鼠 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3259 Solved: 1564[Submit][Statu ...
-
HDU 4403 A very hard Aoshu problem(dfs爆搜)
http://acm.hdu.edu.cn/showproblem.php?pid=4403 题意: 给出一串数字,在里面添加一个等号和多个+号,使得等式成立,问有多少种不同的式子. 思路: 数据量比 ...
随机推荐
-
【maven】 pom.xml内容没有错,但一直报错红叉 解决办法
1.首先看一下下面的这两个项目,一个是新建的,一个是原来的老项目 2.myEcplise中是点击如下图 Maven4MyEcplise, Ecplise中也是右键,只不过点击Mavene而已,两个一样 ...
-
VirtualBox 虚拟 Ubuntu 的一些感想
之前有说过最近在学习Shell,公司及家里的电脑目前都是Windows系统,进行shell学习主要是用一些模拟linux环境的软件,比如banbun.cygwin banbun的功能很强大,集成了oh ...
-
windows下python的包管理器pip安装
pip: A tool for installing and managing Python packages. 要用到第三方包,python的版本就必须是2.7 https://pypi.pyth ...
-
重构23-Introduce&#160;Parameter&#160;Object(参数对象)
有 时当 使用 一个 包含 多 个 参 数 的 方 法 时 , 由 于参 数 过 多 会 导 致 可 读 性 严 重 下 降 , 如 : 有 时当 使用 一个 包含 多 个 参 数 的 方 法 时 , ...
-
Rhythmbox中文乱码解决办法
今天在网络上找到了一个比较好的解决Rhythmbox中文乱码的问题的方法 进入你的音乐文件夹执行如下代码: mid3iconv -e GBK *.mp3 如果没有提示多试几次,有可能系统会提示: py ...
-
C#获取内存图像数据流的方法
背景:有的时候我们已经得到一个图像的内存对象,如Bitmap对象,我们想要获取到这个对象的数据流,可以将其序列化到磁盘上,并且也可以反序列化为内存对象,这个时候就有了如题的问题出现,我搜遍全网就是没有 ...
-
ByteArrayInputStream 和 ByteArrayOutputStream
package java.io; /** * A <code>ByteArrayInputStream</code> contains * an internal buffer ...
-
Ant 简易教程
转载:http://www.cnblogs.com/jingmoxukong/p/4433945.html Ant 简易教程 Apache Ant,是一个将软件编译.测试.部署等步骤联系在一起加以自动 ...
-
【转】Python BeautifulSoup 中文乱码解决方法
这篇文章主要介绍了Python BeautifulSoup中文乱码问题的2种解决方法,需要的朋友可以参考下 解决方法一: 使用python的BeautifulSoup来抓取网页然后输出网页标题,但是输 ...
-
CSS选择器渲染效率
1 浏览器如何识别你的选择器 首先我们需要清楚,浏览器是如何读取选择器,以识别样式,并将相应的样式附于对应的HTML元素,达到美化页面的效果.Chris Coyier曾在<Efficiently ...