/*************************************************************************
*终于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);
	}
}

• 汗……偶加>8的条件就也过来，哪位达人来解释一下…… (2831) FinalLaugh 2004-10-25 21:31:49
  • 好象是可以证明的 (0) 808 2004-10-25 21:35:27
    • 8是大于6最小的偶数吧（也就是说一组数中出现任何大于6的偶数，和出现8对结果没什么影响）我是这样想的，不知对不对 (0) sothink 2004-10-25 21:58:03