BT的第一题

做ACM题计划刚开始就让自己撞了个大钉子，随便选了一个题目，1011，没想到是个超级BT的搜索剪枝题。
Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output

The output should contains the smallest possible length of original sticks, one per line.
Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output

6
5刚看到这个题目觉得还挺简单的，（其实主要原因是有个中文翻译-_-~~). 大概思路就是一开始根据题目的条件有范围确定，接着就是可以回朔搜索了。搜索的时候要剪枝。。.
但是做了就知道根本不是这么简单的。TLE了无数次。
问题的特点就是除了快速求满足一个长度棍子的解之外，还得快速去掉解。
第一个很容易想到的，求解范围，需要整除棍子长度之和，不能小于最大的小棍子长度，个数在小棍子数之内。这些想不到，这题目直接88.
然后搜索的策略，我一开始就走的不对，一开始的方案是让小棍子选择原始棍子的标号搜索，然后剪去原始棍子标号重复。但是这个办法剪枝太难了，因为很容易进入很深的搜索却还对局势没有掌握。放弃。
只能一根根根子去求解，这里面剪枝就多了，棍子排序（自然会想到排序的，快点从大棍子的失败中解脱，并且在后面是的搜索本身呈现顺序性，易于剪枝），然后就是单独原始棍子的后续不要重复的剪枝，还有一个同一长度不在再次使用（在前面排了序，这儿就方便了）的剪枝。有些明显的东西比如长度要刚好满足一个棍子不能叫做剪枝了。上传TLE. TLE. TLE .......
上班比较忙，周末回家才想了一些新办法，但是不知道有些剪枝是不是有问题，最后找到几个可能的剪枝，但是实现起来，代码看着越来越烦了，真不想做了，后来才发现代码里有个保守的错误，这个错误改掉。AC.....大概600MS,虽然不是0MS，我也满意了，痛苦啊。。虽然还有可剪的，但是我已经不想再折磨自己了。
后来才知道1011是个经典的，BT的搜索剪枝题目。
BS 自己。

PS.那个排序用C qsort，速度比泡泡慢 -_~
代码改了很多，看着有点想吐！
#include "stdio.h"

int inp_b[64];
int inp_c = 0;
int min_inp;
int max_inp;
int curL[64];
int curCount[64];

/*int dbg_lay[64][5];*/
int lay[64][64];
int maxC;
int minL;

int used[64];
int usedCount = 0;
static int curSrcIdx;

#define USE(idx)\
do{\
used[idx] = 1;\
curL[curSrcIdx] += inp_b[idx];\
curCount[curSrcIdx] ++;\
usedCount ++;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx] - 1] = inp_b[idx];*/\
lay[curSrcIdx][curCount[curSrcIdx] - 1] = idx;\
}while(0)
#define UNUSE(idx)\
do{\
curL[curSrcIdx] -= inp_b[idx];\
used[idx] = 0; \
curCount[curSrcIdx] --;\
usedCount--;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx]] = 0;*/\
lay[curSrcIdx][curCount[curSrcIdx]] = 0;\
}while(0)

static int tryloop2(int lastIdx)
{
int idx;
int last = 100000;
int ret;
  
if(inp_c - usedCount < idx =" lastIdx;" last =" inp_b[idx];" cursrcidx ="="" ret =" tryloop2(lay[curSrcIdx" cursrcidx ="="" ret ="="" ret ="tryloop2(idx))" ret ="="" i =" 0;" i =" 0;" usedcount =" 0;" cursrcidx =" 0;"> *((int *)p2) )
{
 return -1;
}
else if(*((int *)p1) < *((int *)p2))  {   return 1;  }  else   {   return 0;  } } void b_sort(int inp_b[], int inp_c) {  int i;  int j;  int t;  for(i = inp_c - 1; i >= 0 ; i --)
{
 for(j = 0; j <> inp_b[j])
  {
   t = inp_b[j + 1];
   inp_b[j + 1] = inp_b[j];
   inp_b[j] = t;
  }
 }
}
}
int main(void)
{

int i;


int s = 0;


while(1)
{
 scanf("%d", &inp_c);
 if(inp_c == 0)
 {
  return 0;
 }

 for(i = 0; i < s =" 0;" max_inp =" 0;" min_inp =" 100;" i =" 0;"> inp_b[i])
  {
   min_inp = inp_b[i];
  }
  if(max_inp < max_inp =" inp_b[i];" maxc =" inp_c;"> 0; maxC --)
 {
 
  if(s % maxC == 0)
  {
   minL = s/maxC;
   if(minL < max_inp)
   {
    continue;
   }
  
   //An possible minL;
   if(start_tryloop() == 1)
   {
    break;
   }
  }
 }
}
}