shz

pku 1011 Sticks

 1#include<iostream>
 2#include<algorithm>
 3using namespace std;
 4int len,total,n,i,j,ans,ok,ns;
 5int used[100],stick[100];
 6int cmp(const void *p,const void *q)
 7{
 8  return *(int *)q-*(int *)p;
 9}
10int f(int num,int now,int next)
11{   if(ok==1)  return 1;
12    if(num>=ns) {ok=1;return 1;}
13    int j;
14    for(j=next+1;j<=n;j++)
15    {
16      if(used[j]==0)
17        {
18          if(now+stick[j]==len)
19           {
20              used[j]=1;
21              if(f(num+1,0,0)==1) return 1;
22              used[j]=0;
23              return 0;
24           }
25          else
26          if(now+stick[j]<len)
27            {
28              used[j]=1;
29              if(f(num,now+stick[j],j)==1) return 1;
30              used[j]=0;
31              if(now==0) return 0;
32              while(stick[j+1]==stick[j]&&j<n) j++;
33            }
34        }
35    }
36
37return 0;
38}
39int main()
40{
41  while(scanf("%d",&n)&&n)
42      {
43        total=0;
44        ok=0;
45        for(i=1;i<=n;i++)
46        {
47           scanf("%d",&stick[i]);
48           total+=stick[i];
49        }
50        qsort(stick+1,n,sizeof(int),cmp);
51        for(i=stick[1];i<=total;i++)
52        {
53          if(total%i==0&&ok==0)
54           {  memset(used,0,sizeof(used));
55              ns=total/i;
56              len=i;
57              if(f(1,0,0))break;
58           }
59        }
60        printf("%d\n",len);
61      }
62return 0;
63}
64
65
66

posted on 2008-02-21 19:05 shengzan 阅读(77) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理