簡單dfs hdu 4536 XCOM Enemy Unknown

題目意思：

n個國家，每個國家都有一個恐懼值，每個國家屬於一個洲。外星人攻擊k次，每次攻擊三個不同洲的一個國家，問你作為聯盟指揮最多可以抵抗攻擊的次數。

每次攻擊你都可以支援一個國家，支援後這個國家的恐懼值-2，但其他兩個國家的恐懼值+2，並且其他兩個國家所在大洲的所有其他國家的恐懼值+1.

當有一個國家的恐懼值>5時，任務失敗，不能繼續抵抗攻擊。每個國家的恐懼值最小減少到1。

解題思路：

dfs暴力搜索。

每次有三種選擇，選擇支援哪個國家。

代碼：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int n,m,k;
int st[20],fear[20];
vector<int>myv[6];

struct Node
{
   int a[3];
}fi[110];

bool flag;
int ans;

void dfs(int cur,int *afr)
{
   if(flag)
      return ;
   for(int i=0;i<n;i++)
   {
      if(afr[i]>5) //超過5，說明上一次已經不行了，所以為cur-2
      {
         ans=max(cur-2,ans);
         return ;
      }
   }
   if(cur>k) //能夠抵抗所有的攻擊
   {
      flag=true;
      ans=k;
      return ;
   }
   int tmp[20];

   for(int i=0;i<3;i++) //選擇保護的國家
   {
      //memcpy(tmp,afr,sizeof(afr));
      for(int j=0;j<n;j++)
         tmp[j]=afr[j];
      tmp[fi[cur].a[i]]-=2; //保護國家恐懼值減少2
      if(tmp[fi[cur].a[i]]<1)
         tmp[fi[cur].a[i]]=1;
      for(int j=1;j<=2;j++) //處理其他兩個國家
      {
         int k=(i+j)%3;
         int sta=st[fi[cur].a[k]];
         for(int p=0;p<myv[sta].size();p++)
         {
            tmp[myv[sta][p]]+=1;
         }
         tmp[fi[cur].a[k]]++;
      }
      //printf("cur:%d i:%d\n",cur,i);
     /* for(int j=0;j<n;j++)
         printf("%d ",tmp[j]);
      putchar('\n');*/
      dfs(cur+1,tmp);
   }
}
int main()
{
   //printf("%lf\n",pow(5.0,16.0));
   int t;

   scanf("%d",&t);
   for(int ca=1;ca<=t;ca++)
   {
      scanf("%d%d%d",&n,&m,&k);
      for(int i=0;i<m;i++)
         myv[i].clear();
      for(int i=0;i<n;i++)
      {
         scanf("%d",&st[i]); //所在的洲
         myv[st[i]].push_back(i); //洲中所有的國家
      }
      for(int i=0;i<n;i++)
         scanf("%d",&fear[i]); //每個國家的恐懼值
      for(int i=1;i<=k;i++)
         for(int j=0;j<3;j++)
            scanf("%d",&fi[i].a[j]); //外星人攻擊的國家
      ans=0;
      flag=false;
      dfs(1,fear);
      printf("Case #%d: %d\n",ca,ans);

   }
   return 0;
}