在這邊 judge AC and 0ms , 
but TLE on ACM judge 

can someone tell me why ??

that's my code , thank you!


#include <stdio.h>
#include <stdlib.h>
int cmp(const void * a,const void * b)
{
    return *(int*)b -*(int *)a;
}

int input[1000];

bool record[1000];

bool check(int,int);

bool cut(int len,int i,int n,int count);

int len;

int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("out.h","w",stdout);
    int n,i,sum,k,bound;
    while( EOF != scanf("%d",&n))
    {
         if(n==0) break;
         sum=0;
         for(i=0,k=0;i<n;i++)
         {
            scanf("%d",&input[k]);
            if(input[k]<=50) 
            {
              sum+=input[k];
              record[k]=0;
              k++;
            }
         }
         n=k;
         qsort(input,n,4,cmp);
         bound=sum>>1;
         for(k=input[0]; k<=bound ; k++)
         {
               if(sum %k) continue;
               len=k;
               if(check(sum/k,n))      break;
         }
         
         if(k>bound)printf("%d\n",sum);
         
         else printf("%d\n",len);
    }   
}


bool check(int count,int n)
{
    bool got=true;
    int i=0;
    if(count!=0)
    {
       while(record[i]) i++;
       record[i]=1;
       got=cut(len-input[i],i+1,n,count);
       if(!got) 
           record[i]=0;
    }
    return got;
}

bool cut(int len,int i,int n,int count)
{
    int got=true;
    int k;
    if(len==0) got=check(count-1,n);
    
    else if(i==n) got=false;
    
    else if(!record[i] && input[i]<=len)
    {
        record[i]=1;
        got=cut(len-input[i],i+1,n,count);
        if(!got)
        {
           record[i]=0;
           k=i+1;
           while (input[k]==input[i] &&  k < n) k++;
           
           if(k<n) got=cut(len,k,n,count);

           else got=false;
        }
    }
    
    else  
    {
         k=i+1;
         while(record[k] || input[k]>len) k++;
         if(k<n) got=cut(len,k,n,count);

           else got=false;
    }
    return got;
} 

• Re:請問一下!! (59) frkstyc 2005-11-24 01:09:13
  • Re:請問一下!! (61) hellgod 2005-11-24 01:17:28
    • Re:請問一下!! (153) hellgod 2005-11-24 01:20:16
      • Re:請問一下!! (61) frkstyc 2005-11-24 01:22:01
      • remove sticks with zero length (169) xiaomi 2005-11-24 01:25:19
      • if you have tried to put a stick with length L in a specific position, you need not try another stick with length L (if any) in this position when backtracing (169) xiaomi 2005-11-24 01:30:34
        • Re:if you have tried to put a stick with length L in a specific position, you need not try another stick with length L (if any) in this position when backtracing (69) hellgod 2005-11-24 01:56:54