4456026_wa.cpp

部分PKU上的源码

#include<vector>
#include<iostream>
#include<list>
#include<map>
#include<algorithm>
using namespace std;
int jieguo[1000][1000];
class STAMPS
{
public:
	map<int,int> stamps;
	bool first;
	vector<int> search(int goal,int number)
	{
		vector<int> result;
		if(goal==0) return result;
		if(number==0)
		{
			result.push_back(-1);//失败的标志
			return result;
		}
		for(map<int,int>::iterator iter=stamps.begin();iter!=stamps.end()&&iter->first<=goal;iter++)
		{
			vector<int> temp=search(goal-iter->first,number-1);
			temp.push_back(iter->first);
			sort(temp.begin(),temp.end());
			if(temp[0]==-1) continue;
			jieguo[goal][number]++;
			result=best(result,temp);
		}
		if(result.size()==0) result.push_back(-1);
		return result;
	}
	vector<int> best(vector<int> a,vector<int> b)
	{
		if(a.size()==0) return b;
		if(b.size()==0) return a;
		if(type(a)>type(b)) return a;
		else
			if(type(a)<type(b)) return b;
		if(a.size()<b.size()) return a;
		else if(a.size()>b.size()) return b;
		if(a[a.size()-1]>b[b.size()-1]) return a;
		else return b;
	}
	int type(vector<int> a)
	{
		int types=0;
		for(int count=0;count<a.size();count++)
		{
			int same=1;
			while(a[count+1]==a[count])
			{
				same++;
				count++;
			}
			map<int,int>::iterator iter=stamps.find(a[count]);
			if(iter->second>=same) types+=same;
			else types+=iter->second;
		}
		return types;
	}
	bool w_tie(vector<int> a)
	{
		int sum=0;
		for(int count2=0;count2<a.size()-1;count2++)
		{
			sum+=a[count2];
		}
		if(jieguo[sum][3]>=1) return true;
		for(int count=0;count<a.size();count++)
		{
			int same=1;
			while(a[count+1]==a[count])
			{
				same++;
				count++;
			}
			map<int,int>::iterator iter=stamps.find(a[count]);
			//cout<<iter->second;
			if(iter->second!=1&&iter->second!=same) return true;
		}
		return false;
	}
	void read()
	{
		stamps.clear();
		memset(jieguo,0,sizeof(jieguo));
		int temp;
		cin>>temp;
		while(temp!=0)
		{
			map<int,int>::iterator iter=stamps.find(temp);
			if(iter!=stamps.end()) 
			{
				int temp2=iter->second;
				stamps.erase(iter);
				stamps.insert(pair<int,int>(temp,temp2+1));
				//cout<<iter->second;
			}
			else
			{
				stamps.insert(pair<int,int>(temp,1));
			}
			cin>>temp;
		}
		cin>>temp;
		while(temp!=0)
		{
			vector<int> best=search(temp,4);
			if(first)
			{
				first=false;
			}
			else
			{
				cout<<'\n';
			}
			if(best[0]==-1)
			{
				cout<<temp<<" ---- none";
			}
			else
			if(!w_tie(best))
			{
				cout<<temp<<" ("<<type(best)<<"):";
				for(int count=0;count<best.size();count++)
				{
					cout<<" "<<best[count];
				}	
			}
			else
			{
				cout<<temp<<" ("<<type(best)<<"): tie";
			}
			cin>>temp;
		}

	}
};
int main()
{
	STAMPS a;
	char temp;
	a.first=true;
	do
	{
		a.read();
	}
	while((temp=getchar())=='\n');
	return 0;
}