#include <stdio.h>
#include <algorithm>
using namespace std;
#define BUF 60
#define MIN(a,b) (a > b ? b : a)

/*
算法：
1.统计所有的可能取值
2.枚举，找出所有可能的组合
3.对每一种组合根据题意进行判优
4.分析最优解，看是否有重复的可能
*/
typedef struct
{
	int key,times;
}Node;//key:对应的数值，times:在原输入中该数出现的次数
int ptr;//出现的不同数值数量
Node list[BUF]; //数值表
bool dup = false;//判重
int sam[BUF];//原输入

bool flags[BUF];//辅助位
int result_level[5];//记录当前结果
int result[BUF];//记录当前结果表
int best_result_item[BUF];//当前最好结果表
int best_result[5];//当前最好结果
int Best_Types = 0;//当前最好结果邮票种数
int Best_Nums; //当前最好结果用邮票数

void OutPut(int req)
{
	printf("%d ",req);
	if(!Best_Types)
	{
		printf("---- none\n");
		return;
	}
	printf("(%d):",Best_Types);
	if(dup)
	{
		printf(" tie\n");
		return;
	}
	for(int i = 1;i <= Best_Nums;i ++)
	{
		if(best_result_item[best_result[i]] != list[best_result[i]].times && list[best_result[i]].times != 1)//若最优解的判重，如果当前最优解和该数出现次数不一致且该数出现次数不为1时必然有不同的解
		{
			printf(" tie\n");
			return;
		}
	}
	for(int i = 1;i <= Best_Nums;i ++)
		printf(" %d",list[best_result[i]].key);
	putchar('\n');
}

void Judge(int level)
{
	int use_num = 0;
	memset(result,0,sizeof(result));
	for(int i = 1;i <= level;i ++)
	{
		result[result_level[i]] ++;
		flags[result_level[i]] = true;
	}
	for(int i = 1;i <= level;i ++){
		if(flags[result_level[i]])
			use_num += MIN(result[result_level[i]],list[result_level[i]].times);
		flags[result_level[i]] = false;
	}
	if(use_num > Best_Types || (use_num == Best_Types && Best_Nums >= level) && (Best_Nums > level || best_result[Best_Nums] < result_level[level]))
	{
		dup = false;
		Best_Types = use_num;
		Best_Nums = level;
		memcpy(best_result,result_level,sizeof(result_level));
		memcpy(best_result_item,result,sizeof(result));
	}
	else if(use_num == Best_Types && Best_Nums == level && (best_result[Best_Nums] == result_level[level]))
		dup = true;//判重
}

void HandleInput()
{
	int req;
	while(1)
	{
		Best_Types = 0;
		Best_Nums = 1 << 30;
		scanf("%d",&req);
		if(!req)
			break;
		for(int n = 1;n <= ptr;n ++)//4重枚举
		{
			int now_1 = req - list[n].key;
			result_level[1] = n;
			if(!now_1)
				Judge(1);
			for(int k = n;k <= ptr;k ++)
			{
				int now_2 = now_1 - list[k].key;
				result_level[2] = k;
				if(!now_2)
					Judge(2);
				for(int j = k;j <= ptr;j ++)
				{
					int now_3 = now_2 - list[j].key;
					result_level[3] = j;
					if(!now_3)
						Judge(3);
					for(int i = j;i <= ptr;i ++)
					{
						result_level[4] = i;
						if(now_3 == list[i].key)
							Judge(4);
					}
				}
			}
		}
		OutPut(req);
	}
}

int Input()
{
	ptr = 0;
	if(scanf("%d",&sam[1]) == EOF)
		return 0;
	int k;
	for(k = 2;sam[k - 1];k ++)
	{
		scanf("%d",&sam[k]);
		if(!sam[k])
			break;
	}
	sort(sam,sam + k );//保证非减
	int nowkey = -1;
	for(int i = 1;i < k;i ++)
	{
		if(nowkey != sam[i])//加入数表
		{
			nowkey = sam[i];
			Node no;
			no.key = nowkey;
			no.times = 1;
			list[++ ptr] = no;
		}
		else
			list[ptr].times ++;
	}
	return ptr;
}

int main()
{
	int n;
	while(n = Input())
		HandleInput();
	return 0;
}

• Re:AC..0ms..代码加注释．．．代码好长。。欢迎吐槽。。 (15) KevinSayHi 2013-03-31 13:45:57