hdu4536-XCOM Enemy Unknown(爆搜)

XCOM-Enemy Unknown是一款很好玩很经典的策略游戏. 在游戏中,由于未知的敌人--外星人入侵,你团结了世界各大国家进行抵抗.

随着游戏进展,会有很多的外星人进攻事件.每次进攻外星人会选择3个国家攻击,作为联盟的指挥者,你要安排有限的联盟军去支援其中一个国家,抵抗进攻这个国家的外星人.

战斗胜利之后这个被支援的国家恐慌值就会-2点(恐慌值最少减为1),而其他两个未被支援的国家恐慌值就会+2点,同时和这两个国家在相同大洲的其他国家恐慌值也会+1点. 当一个国家的恐慌值超过5点,这个国家就会对联盟失去信心从而退出联盟. 现在给你外星人将会进攻的地点,问你最多能在不失去任何一个国家信任的情况下抵挡多少次外星人的进攻.

Input

第一行有一个整数T代表接下来有T组数据每组数据第一行是三个整数,n,m,k分别代表联盟国家的个数，大洲的个数，外星人的进攻次数. 第二行是n个数字代表各个国家所属的大洲(大洲序号从0到m-1) 第三行是n个数字代表各个国家初始的恐慌值接下去k行代表外星人进攻每行有三个数字,表示该次外星人进攻的国家(国家序号从0到n-1)
[Technical Specification] 0<T<=100 8<n<=16 2<m<=5 0<k<=100 0<初始恐慌值<=5 每个州至少有三个国家每次外星人进攻一定发生在不同州的三个国家

Output

首先输出case数(见sample),接着输出在不失去任何一个国家的情况下能抵挡外星人进攻最多的次数.

Sample Input

1

9 3 2

0 0 0 1 1 1 2 2 2

3 3 3 3 3 3 3 3 3

0 3 6

0 3 6

Sample Output

Case #1: 1

题意我就不说了

解析：刚开始看这题的时候以为要搜100层，岂不是爆了，然而。。。。。。其实根本到不了那么深，所以爆搜即可。

代码

#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+7;
const double eps=1e-7;
const int maxn=20;
int N,M,K;
vector<int> G[maxn];
int bel[maxn],val[maxn],ans;
struct Atk
{
    int x,y,z;
    Atk(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
}atk[105];
bool work(int a,int y)
{
    for(int i=0;i<G[a].size();i++)
    {
        int c=G[a][i];
        if(c==y) val[c]+=2;  
        else val[c]+=1;
        if(val[c]>5) return false;
    }
    return true;
}
void dfs(int step)
{
    ans=max(ans,step);
    if(step>=K) return;
    int B[maxn];
    for(int i=0;i<N;i++) B[i]=val[i];
    Atk& t=atk[step];
    int x=t.x,y=t.y,z=t.z;
    val[x]-=2;
    if(val[x]<1) val[x]=1;
    if(work(bel[y],y)&&work(bel[z],z)) dfs(step+1);
    for(int i=0;i<N;i++) val[i]=B[i];
    val[y]-=2;
    if(val[y]<1) val[y]=1;
    if(work(bel[x],x)&&work(bel[z],z)) dfs(step+1);
    for(int i=0;i<N;i++) val[i]=B[i];
    val[z]-=2;
    if(val[z]<1) val[z]=1;
    if(work(bel[x],x)&&work(bel[y],y)) dfs(step+1);
    for(int i=0;i<N;i++) val[i]=B[i];
    return;
}
int main()
{
    int T,Case=0;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<maxn;i++) G[i].clear();
        scanf("%d%d%d",&N,&M,&K);
        int x,y,z;
        for(int i=0;i<N;i++)
        {
            scanf("%d",&x);
            bel[i]=x;     
            G[x].push_back(i);
        }
        for(int i=0;i<N;i++) scanf("%d",&val[i]);
        for(int i=0;i<K;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            atk[i]=Atk(x,y,z);
        }
        ans=0;
        dfs(0);
        printf("Case #%d: %d
",++Case,ans);
    }
    return 0;
}

View Code