#include<stdio.h>
#include<string.h>
bool opt[60000];
int num=0;
int mid,max;
int stone[7];
int input()
{
    scanf("%d%d%d%d%d%d",&stone[1],&stone[2],&stone[3],&stone[4],&stone[5],&stone[6]);
    if (!stone[6]&&!stone[1]&&!stone[2]&&!stone[3]&&!stone[4]&&!stone[5]) 
	   {return 1;}
    num++;
    printf("Collection #%d:\n",num);
    /*mid=0;
    for (int i=1;i<=6;i++) 
		mid+=stone[i]*i;
    if (mid % 2 ==1) 
    {
        printf("Can't be divided.\n\n");
        return 2;
    }//如果总和为奇数，则剪枝 
    else mid/=2;//得到每个人应得的数目 */
    mid=0;
 		  for (int i=1;i<=6;i++)
 		  {	
	 	  	  
	 		  mid+=stone[i]*i;
          }
  		  if (mid==0)
  		  	 return 1;
	  	  if (mid%2==1)
	  	  {
	       	 //printf("Collection #%d:\n",count);
	       	 printf("Can't be divided.\n\n");
	       	 //count++;
   	 		 return 2;
          }
          else mid/=2;
    return 0;
}

void dp()
{
    memset(opt,0,60000);
    opt[0]=true;
    max=0;//max代表目前满足opt[k]==true这一条件的k的最大值
    
    for (int i=1;i<=6;i++)
    {
        if (stone[i]>0)
        {
            for(int j=max;j>=0;j--)
            if (opt[j])
            {
                if (opt[mid]) 
                {
                    printf("Can be divided.\n\n");
                    return;
                }
                for (int k=1;k<=stone[i];k++)
                {
                    if (j+k*i>mid || opt[j+k*i]) 
					   break;
                    opt[j+k*i]=true;
                }
            }
        }
        max=max+i*stone[i];
        if (max>mid) max=mid; 
    }
    printf("Can't be divided.\n\n");
}

int main()
{
    while (1)
    {
        int t=input();
        switch (t)
        {
            case 1 : return 0;
            case 2 : continue;
            default : dp();
        }
        
    }
    return 0;
}
上面的代码在算“2 0 0 0 0 0”时候出的是can't，但可以AC……

• Re:此题有bug (15) fireleg 2009-07-14 20:18:15