> /*************************************************************************
> *终于AC了！辛苦辛苦^0^一起切磋java啊！呵呵
> *WA了4、5遍，都不知道是哪里的问题。后来改了几个地方就AC了。忘了错在哪里。
> *结合了一点点动规的思想：如果可以到达value[i]，则考虑可以到达的value[j]。
> *由于本人对DP不太懂，所以想出来的DP也可能很令人费解。*~*罪过罪过
> *但是，始终不明白为什么是8？这个我是抄别人的。
> *************************************************************************/
> import java.io.*;
> import java.util.*;
> 
> public class Main
> {
> 	public static void main(String[] args)throws Exception
> 	{
> 		BufferedReader cin=new BufferedReader(new
> 								InputStreamReader(System.in));
> 		String str;
> 		StringTokenizer strtoken;
> 		int  [] m=new int[6];
> 		int no=0;
> 		int i,j,k;
>         //Read in the first case
> 		str=cin.readLine();
> 		strtoken=new StringTokenizer(str);
> 		for(i=0;i<6;++i)
> 			m[i]=Integer.parseInt(strtoken.nextToken());
> 		while(!(m[1]==0&&m[2]==0&&m[3]==0&&m[4]==0&m[5]==0&m[0]==0))
> 		{   //Make it smaller
> 			for(i=0;i<6;++i)
> 				if(m[i]>8){//始终不明白为什么是8？谁能证明啊？
> 					if(m[i]%2==0)m[i]=8;
> 					else m[i]=7;
> 				}
>             
> 			int total=0;
> 			for(i=0;i<6;++i)
> 				if(m[i]>0)
> 					total+=m[i]*(i+1);
> 			if(total%2==1)//Total is odd, so can't be divided!
> 				System.out.println("Collection #"+(++no)+
> 					":\nCan't be divided.\n");
> 			
> 			else{
> 				boolean flag=false;
> 				for(i=0;i<6;++i)//Special case，开始的时候这里可能也WA了！
> 					if(m[i]>0&&(total/2)>i&&(total/2)%(i+1)==0&&
> 						(total/2)/(i+1)<=m[i]){
> 						System.out.println("Collection #"+
> 							(++no)+":\nCan be divided.\n");
> 						flag=true;break;
> 					}
>                 //Normal case  
> 				if(flag==false){
> 
> 					BitSet value=new BitSet(total+1);
> 					int []  last=new int[total+1];
> 					total/=2;
> 					value.set(0);
> 					Arrays.fill(last,0);
> 
> 					for(i=0;i<total;++i)
> 						if(value.get(i)){//已经到达的一个value值
> 
> 							for(j=last[i];j<6;++j)//last是指到达这个value值
> 							                //使用的marble的种类（编号最小）
> 								if(m[j]>0){
> 									for(k=1;k<=m[j];++k)
> 									{
> 										int temp=i+(j+1)*k;
> 										           //可以到达的另一个value值
> 										if(temp>total)break;
> 										value.set(temp);
> 										if(last[temp]==0||last[temp]>j+1)
> 											last[temp]=j+1;//WA在这里了！呵呵
> 									}
> 								}
> 							if(value.get(total))break;
> 						}
> 
> 					if(value.get(total))
> 						System.out.println("Collection #"+(++no)+
> 						":\nCan be divided.\n");
> 					else
> 						System.out.println("Collection #"+(++no)+
> 						":\nCan't be divided.\n");
> 
> 				}
> 			}
> 			//New Case
>             str=cin.readLine();
> 			strtoken=new StringTokenizer(str);
> 			for(i=0;i<6;++i)
> 				m[i]=Integer.parseInt(strtoken.nextToken());
> 		}
> 	//System.exit(0);
> 	}
> }
> 

• 好象是可以证明的 (0) 808 2004-10-25 21:35:27
  • 8是大于6最小的偶数吧（也就是说一组数中出现任何大于6的偶数，和出现8对结果没什么影响）我是这样想的，不知对不对 (0) sothink 2004-10-25 21:58:03