简单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;
}

补充：软件开发 , C++ ,

上一个：poj1934 Trip
下一个：poj3227