Posted on 2006-11-30 00:34
oyjpart 阅读(4000)
评论(15) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
这道题作的我真的是悲喜交加阿。。。做完之后。。。长舒一口气。。推荐大家去做！！！
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。我想 用预先得到所有可拼凑长度来ＨＡＳＨ 发现太大．．．
3。然后我想对每个长棍分开搜索．．．
4。后来我又用记录数目的方法搜 似乎更慢．．．
终于发现真正重要的剪枝！
1.当一个正好可以填满的时候 就不用考虑比他小的去填了
2.一大段的第一个小段如果不成立直接返回到上一大段
这才是重要的剪枝
同时还有一个 要预防反复搜索同一关键码 给出下面的测试数据
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
呵呵 其实AC的程序里面有一大部分都过不了这个数据！包括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;
}