oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

Sticks
Time Limit:1000MS? Memory Limit:10000K
Total Submit:18973 Accepted:4421

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 















1。我從大到小搜索了哇 沒用。。。 
2。我想　用預(yù)先得到所有可拼湊長度來ＨＡＳＨ　發(fā)現(xiàn)太大．．．
3。然后我想對每個(gè)長棍分開搜索．．． 
4。后來我又用記錄數(shù)目的方法搜　似乎更慢．．． 
終于發(fā)現(xiàn)真正重要的剪枝！
1.當(dāng)一個(gè)正好可以填滿的時(shí)候 就不用考慮比他小的去填了
2.一大段的第一個(gè)小段如果不成立直接返回到上一大段
這才是重要的剪枝 
同時(shí)還有一個(gè) 要預(yù)防反復(fù)搜索同一關(guān)鍵碼 給出下面的測試數(shù)據(jù)
64
40 40 40 40 40 40 40 40 40 40 40 40 40 
40 40 40 40 40 40 40 40 40 40 43 42 42 
41 10 4 40 40 40 40 40 40 40 40 40 40 
40 40 40 40 40 40 40 40 40 40 40 40 40 
40 40 40 40 40 40 40 40 40 40 40 40 
0
呵呵 其實(shí)AC的程序里面有一大部分都過不了這個(gè)數(shù)據(jù)！包括0MSAC的！

呵呵 過了之后 心情好啊~`哈哈
//Solution
//by optimistic
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int nss;
int ss[70];
int used[70];
int totss;
int maxss;
int len;

int cmp(const void * a, const void * b)
{
?return (*(int *)b) - (*(int *)a);
}

int search(int times, int rest, int pos)
{
?int flag = 0;
?if(rest == len) flag = 1; //第一種剪枝
?int i;
?if(times == totss/len) return 1;
?for(i = pos; i<nss; i++)
??if(!used[i])
??{
???if(rest == ss[i])
???{
????used[i] = 1;
????if(search(times+1, len, 0))?return 1;
????used[i] = 0;
??? ?return 0;????????????????????? //第二種剪枝??????????????????????????????????????????????????????????????????? 
???}
???else if(ss[i]<rest)
???{
????used[i] = 1;
????if(search(times, rest-ss[i], i+1)) return 1;
????used[i] = 0;
????if(flag) return 0;
????while(ss[i] == ss[i+1]) i++;
???}
???else if(flag) return 0;
??}
?return 0;
}

int main()
{
//?freopen("t.in", "r", stdin);
?int i;
?while(scanf("%d", &nss), nss>0)
?{
??memset(ss, 0, sizeof(ss));
??totss = maxss = 0;
??for(i=0; i<nss; i++)
??{
???scanf("%d", &ss[i]);
???totss += ss[i];
???if(ss[i]>maxss) maxss = ss[i];
??}
??qsort(ss, 70, sizeof(ss[0]), cmp);
??for(i=maxss; i<=totss; i++)
??{
???if(i==totss) 
???{printf("%d\n", totss); break;}
???if(totss%i==0)
???{?????
????memset(used, 0, sizeof(used));
????len = i;

????if(search(1, len, 0)) {printf("%d\n", i); break;}
???}
??}
?}
?return 0;
}