XCOM Enemy Unknown 简单的dfs() 枚举就行,不过有个用二进制压缩的没看懂

Problem Description

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

Hint

第一次如果选择了0,那么3和6的恐慌值就会增加到5,第二次不管怎么选择,3和6总会有一个超过5.

***************************************************************************************************************************

简单dfs(),可用二进制优化（这个没看懂啊）

***************************************************************************************************************************

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdio>
 6 #include<vector>
 7 using namespace std;
 8 int st[1001],fear[1001];
 9 int cas,ans;
10 int n,m,k,i,j;
11 bool flag;
12 struct node
13 {
14     int a[3];
15 }fi[1001];//此处还可用二维数组
16 vector<int>mvy[6];
17 void dfs(int cur,int *afr)
18 {
19     if(flag)//剪枝
20         return;
21     for(int it=0;it<n;it++)//剪枝
22     {
23         if(afr[it]>5)
24         {
25             ans=max(ans,cur-2);
26             return;
27         }
28     }
29     if(cur>k)//剪枝
30     {
31         flag=true;
32         ans=k;
33         return;
34     }
35     int tmp[20];//为了保持原始数据，（其实就是还原）
36     for(int it=0;it<3;it++)//考虑3种情况
37     {
38         for(int jt=0;jt<n;jt++)
39          tmp[jt]=afr[jt];
40         tmp[fi[cur].a[it]]-=2;
41         if(tmp[fi[cur].a[it]]<1)//此处必须判断
42           tmp[fi[cur].a[it]]=1;
43         for(int jt=1;jt<=2;jt++)
44         {
45             int k=(it+jt)%3;
46             int sta=st[fi[cur].a[k]];
47             for(int kt=0;kt<mvy[sta].size();kt++)
48             {
49                 tmp[mvy[sta][kt]]+=1;
50             }
51             tmp[fi[cur].a[k]]+=1;
52 
53         }
54         dfs(cur+1,tmp);
55     }
56 
57 }
58 int main()
59 {
60     scanf("%d",&cas);
61     int ca=0;
62     while(cas--)
63     {
64       ++ca;
65       scanf("%d%d%d",&n,&m,&k);
66       for(i=0;i<m;i++)
67        mvy[i].clear();
68       for(i=0;i<n;i++)
69       {
70           scanf("%d",&st[i]);
71           mvy[st[i]].push_back(i);
72       }
73       for(i=0;i<n;i++)
74        scanf("%d",&fear[i]);
75       for(i=1;i<=k;i++)
76        for(j=0;j<3;j++)
77        {
78           scanf("%d",&fi[i].a[j]);
79        }
80        ans=0;
81        flag=false;
82        dfs(1,fear);
83        printf("Case #%d: %d
",ca,ans);
84     }
85     return 0;
86 }
87 //其实就是枚举

View Code