原题http://acm.hdu.edu.cn/showproblem.php?pid=4536

XCOM Enemy Unknown

Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 851    Accepted Submission(s): 257

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


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



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

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

Case #1: 1

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

//这道题目很明显是要用沈搜，由于数据都不是很大，所以最后的时间是0秒
//具体的操作过程是每次都要枚举所有的情况。如果满足则继续深搜下去，如果不满足，则将那些值都还原。要主要搜索最后结束的 条件
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>
#include <malloc.h>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define N 20
#define M 100 + 10
int attack[M][3];
int num[N];
int sum[N];
int n,m,k;
int max_cn;

int max(int a,int b){
	return a>b?a:b;
}

void DFS(int cn){
	int i;
	if(cn >= k){//这种情况是因为如果第一次就可以一直搜下去到最后
		max_cn = k;
		return ;
	}
	if(max_cn >= k){//满了。就结束搜索
		//max_cn = k;
		return ;
	}
	int a[3];
	int b[3];
	int j;
	for(i=0;i<3;i++){
		a[0] = attack[cn][i];//救助的国家的编号
		a[1] = attack[cn][(i+1)%3];//其余两个国家的编号
		a[2] = attack[cn][(i+2)%3];
		b[0] = sum[a[0]];//先保存下来这三个国家的值
		b[1] = sum[a[1]];
		b[2] = sum[a[2]];
		sum[a[0]]= sum[a[0]]-2;
		if(sum[a[0]] < 1){
			sum[a[0]] = 1;
		}
		sum[a[1]]+=2;
		sum[a[2]]+=2;
		for(j=0;j<n;j++){
			if(num[j]==num[a[1]] && j!=a[1]){
				sum[j]++;
			}
			if(num[j]==num[a[2]] && j!=a[2]){
				sum[j]++;
			}
		}
		int flag = 1;
		for(j=0;j<n;j++){
			if(sum[j] > 5){//如果有大于5的情况就说明不能继续进行下去了
				max_cn = max(cn,max_cn);//记录下当前最大的值
				flag = 0;
			}
		}
		if(flag == 1){//如果可以，则继续搜索下去
			DFS(cn+1);
		}
		//还原
		sum[a[0]] = b[0];
		sum[a[1]] = b[1];
		sum[a[2]] = b[2];
		for(j=0;j<n;j++){
			if(num[j]==num[a[1]] && j!=a[1]){
				sum[j]--;
			}
			if(num[j]==num[a[2]] && j!=a[2]){
				sum[j]--;
			}
		}
	}
}

int main(){
	int T;
	int cas,i;

	while(~scanf("%d",&T)){
		memset(num,0,sizeof(num));
		memset(sum,0,sizeof(sum));
		memset(attack,0,sizeof(attack));
		for(cas=1;cas<=T;cas++){
			scanf("%d%d%d",&n,&m,&k);
			for(i=0;i<n;i++){
				scanf("%d",&num[i]);
			}
			for(i=0;i<n;i++){
				scanf("%d",&sum[i]);
			}
			for(i=0;i<k;i++){
				scanf("%d%d%d",&attack[i][0],&attack[i][1],&attack[i][2]);
			}
			max_cn = 0;
			//printf("Case #%d: %d",cas);
			DFS(0);
			printf("Case #%d: %d\n",cas,max_cn);
		}
	}

	return 0;
}