import java.util.*;
public class Main {
	static int stamps[]=new int[100];
	static int refer[]=new int[100],t_refer[]=new int[100];
	static int stampnum;
	static int maxdef,minnum,maxnum;
	static int nowdef,nowminnum,nowmaxnum;
	static boolean tie;
	static void deal(int s,int rn,int r)//回溯
	{
		if(r==0)
		{
			if(nowdef>maxdef||(nowdef==maxdef&&nowminnum<minnum)||(nowdef==maxdef&&nowminnum==minnum&&nowmaxnum>maxnum))
			{
				tie=false;
				maxdef=nowdef;
				minnum=nowminnum;
				maxnum=nowmaxnum;
				for(int i=1;i<=stampnum;i++) refer[i]=t_refer[i];
			}
			else if (nowdef==maxdef&&nowminnum==minnum&&nowmaxnum==maxnum) tie=true;
			else return;
		}
		else if(rn<1||r<1||s>stampnum) return;
		else if(nowdef+rn<maxdef) return;//剪枝1
		else if(r-stamps[s]<0) return;//剪枝2
		else
		{
			//----------case1&&cacse2-----------
			int t_mn=nowmaxnum;
			boolean flag=true;
			for(int i=s+1;i<=stampnum;i++)
				if(t_refer[i]>0) flag=false;
			if(flag) nowmaxnum=stamps[s];
			nowminnum++;
			 t_refer[s]++;
			//---------------------------------
			 nowdef++;
		    deal(s+1,rn-1,r-stamps[s]);
		    nowdef--;
		    deal(s,rn-1,r-stamps[s]);    
		    //---------------------------------
		    t_refer[s]--;
		    nowmaxnum=t_mn;
		    nowminnum--;
		    //-------end----------------------
		    
		    deal(s+1,rn,r);
			
		}
	}
	public static void main(String arg[])
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNextInt())
		{
			stampnum=0;
			
			while(true)
			{
				int temp=in.nextInt();
				if(temp==0) break;
				else
				{
					stamps[++stampnum]=temp;
				}
			}
			Arrays.sort(stamps,1,stampnum+1);
			while(true)
			{
				int temp=in.nextInt();
				if(temp==0) break;
				else
				{
					Arrays.fill(t_refer, 0);
					tie=false;
					maxdef=nowdef=maxnum=nowmaxnum=nowminnum=0;
					minnum=999;
					if(stamps[stampnum]*4>=temp) deal(1,4,temp);
					if(maxdef!=0)
					{
						if(tie) System.out.println(temp+" ("+maxdef+"): tie");
						else
						{
							System.out.print(temp+" ("+maxdef+"):");
							for(int i=1;i<=stampnum;i++)
                                for(int j=1;j<=refer[i];j++) System.out.print(" "+stamps[i]);
							System.out.println();
						}
					}
					else System.out.println(temp+" ---- none");
					
				}
			}
		}
		
	}

}

• Re:气死气死。。一个小失误让我WA了N次，把代码贴出来吧 (30) yzhw 2009-02-08 22:02:12