oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

PKU 1011 Sticks

Posted on 2006-11-30 00:34 oyjpart 阅读(3974) 评论(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。我想 用预先得到所有可拼凑长度来HASH 发现太大...
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;
}




Feedback

# re: PKU 1011 Sticks   回复  更多评论   

2007-04-13 23:40 by Jun Wang
if(search(1, len, 0)) {printf("%d\n", i); break;}
是不是要改成 if(search(0, len, 0)) {printf("%d\n", i); break;} ??

# re: PKU 1011 Sticks   回复  更多评论   

2007-07-22 19:28 by Typhoooooooooooooooooooooooooooooooooon
感谢你那两个重要的剪枝哈

# re: PKU 1011 Sticks   回复  更多评论   

2007-10-24 11:00 by delguoqing
你上面这个测试数据的ouput是多少?

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-04 23:46 by mango
你测这个... 你的半天也出不来...
64
40 40 30 35 35 26 15 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 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40

40

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-05 09:02 by oyjpart
的确啊,很强大的数据啊

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-05 18:42 by zoyi
答案是454~~可是我的程序居然是wa~5555555555

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-05 20:10 by oyjpart
哦?你怎么知道答案啊

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-06 19:43 by zoyi
我的程序跑出来的啊~~难道你怀疑我跑的是错误的???哈哈@oyjpart

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-07 12:49 by mango
哎......这个数据真变态...烦死了 呵呵

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-07 21:06 by oyjpart
哦。。。你过题了没

# re: PKU 1011 Sticks   回复  更多评论   

2008-05-22 15:59 by zsong
我跑出454了,很快,不过也是wa

# re: PKU 1011 Sticks   回复  更多评论   

2008-08-12 20:45 by zjh777007
谁能告诉我
“一大段的第一个小段如果不成立直接返回到上一大段”
什么意思?

# re: PKU 1011 Sticks   回复  更多评论   

2008-08-12 20:53 by oyjpart
现在由一个当前情况S.
这个时候比如有一个大棍子,长度为20,现在尝试在其中放入一个长度为5的小棍子。结果深搜得到的结果是不可行,则认为当前情况是无解的。
因为这个5长度的小棍子放不了这个大棍子,绝对放不了任何一根大棍子。

# re: PKU 1011 Sticks   回复  更多评论   

2008-11-30 11:29 by abc
#include<iostream>
#include<string>
#include<fstream>
#include<vector>
#include<ctime>
using namespace std;
fstream fin("e:\\office\\txt\\acmin.txt");
int l[65];
int s,t,min,sum=0,len;
int max2;
int count=0;
int c=0;
static int used[65];
int search(int leni, int s){
if(leni==0) return 100;
t=s;
int count=0;
while(l[t]>leni||used[t]){
t--;
if(t==0){
//break;
return 0;
}
}
used[t]=1;
count++;
if(l[t]<=leni){
int se=search(leni-l[t],s-1);

if(se>=100){
count+=(se-100);
//if((leni-l[t])!=0){
//if(count<s){
c=1;
for(int i=1;i<=s;i++)c*=used[i];
if(!c){
int sea=search(len,s-1);
if(sea>=100){
count+=(sea-100);
return count+100;
}/*else{
return 0;
}*/
//}
}
}
/*else{
return 0;
}*/
}
count+=100;
return count;
}
int main(){
cin>>s;
while(s){

max2=0;
sum=0;
count=0;
for(int i=0;i<65;i++)used[i]=0;
for(int i=1;i<=s;i++){
cin>>l[i];
if(l[i]>max2){
max2=l[i];
}
sum+=l[i];
}
for(int i=0;i<=s;i++){
for(int j=0;j<s-i;j++){
if(l[j]>l[j+1]){
int temp=l[j];
l[j]=l[j+1];
l[j+1]=temp;
}
}
}
cout<<"sum"<<sum<<endl;
for(int i=max2;i<=sum;i++){
len=i;

for(int j=0;j<65;j++)used[j]=0;
if(sum%i!=0)continue;

int k=search(i,s);

if(k>100){

if((k-100)==s){cout<<i<<endl;break;}
}else{
continue;
}
}
cin>>s;
}

}













# re: PKU 1011 Sticks   回复  更多评论   

2008-11-30 11:30 by abc
各位高手帮忙看一下上面的程序有什么错误,万分感激!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理