4558171_re.cpp

部分PKU上的源码

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int stamps[30];
int number;
int ns;
int goal;
bool tie;
bool can_find;

int sum[5];
int at_search[5];
int type[5];
int max_s[5];

int bre[5];
int bsnumber;
int btype;
int bmax_s;

int cmp(const void *p1,const void *p2)
{
	return (*(int *)p1-*(int *)p2);
}
void getnewone(int searchn)
{
	for(int count=1;count<=searchn;count++)
	{
		bre[count]=stamps[at_search[count]];
	}
	bsnumber=searchn;
	btype=type[searchn];
	bmax_s=max_s[searchn];
}
void deal(int searchn,int now)
{
	if(searchn==0)
	{
		memset(at_search,0,sizeof(at_search));
		sum[0]=0;
		type[0]=0;
		max_s[0]=0;
		deal(1,0);
		return;
	}
	if(searchn==5) return ;
	int count=now;
	while(count<number)
	{
		if(stamps[count]+sum[searchn-1]==goal)
		{
			at_search[searchn]=count;
			if(searchn==1)type[searchn]=1;
				else 
					if(count!=at_search[searchn-1]) type[searchn]=type[searchn-1]+1;
					else type[searchn]=type[searchn-1];
			max_s[searchn]=stamps[count];

			if(can_find==false)
			{
				getnewone(searchn);
			}
			else
			{
				if(btype<type[searchn]) getnewone(searchn);
				else
					if(btype==type[searchn])
					{
						if(bsnumber>searchn) getnewone(searchn);
						else 
							if(bsnumber==searchn) 
							{
								if(bmax_s<max_s[searchn]) getnewone(searchn);
								else if(bmax_s==max_s[searchn]) tie=true;
							}
					}
			}
			can_find=true;
		}
		else 
			if(stamps[count]+sum[searchn-1]<goal)
			{
				at_search[searchn]=count;
				sum[searchn]=stamps[count]+sum[searchn-1];
				if(searchn==1)type[searchn]=1;
				else 
					if(count!=at_search[searchn-1]) type[searchn]=type[searchn-1]+1;
					else type[searchn]=type[searchn-1];
				max_s[searchn]=stamps[count];
				deal(searchn+1,count);
			}
		else return;
		count++;
	}
	
}

int main()
{
	int i=0;
	number=0;
	while(cin>>stamps[i])
	{
		i++;
		if(stamps[i-1]==0)
		{
			qsort(stamps,number,sizeof(int),cmp);
			while(cin>>goal)
			{
				tie=false;
				can_find=false;
				if(goal==0) break;
				deal(0,0);
				if(can_find)
				{
					if(tie)
					{
						printf("%d (%d): tie\n",goal,btype);
					}
					else
					{
						printf("%d (%d): ",goal,btype);
						for(int count=1;count<=bsnumber;count++)
						{
							printf("%d ",*(bre+count));
						}
						printf("\n");
					}
				}
				else
				{
					printf("%d ---- none\n",goal);
				}

			}
			number=0;
			i=0;
		}
		else number++;
	}
	return 0;
}