HDOJ搜索专题之Sticks

题目数学模型：给定n个正整数，现要将这n个数分成k组，且满足每组的和都相等。求最多能分多少组。

这题是经典的剪枝搜索题，原题来自PKU。下面的程序虽然AC了，但是跑不动POJ中discuss中的那组BT数据。

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <vector>
 5 #define MAX(a,b) ((a)>(b)?(a):(b))
 6 #define N 64
 7 using namespace std;
 8 vector<int>stick[N];
 9 int len[N],vis[N],n,sum,yes;
10 int cmp(const void *a,const void *b)
11 {
12   return *(int*)b-*(int*)a;
13 }
14 void dfs(int k,int l,int L)
15 {
16   int i;
17   if(l==L)
18   {
19     dfs(k+1,0,L);
20     return;
21   }
22   if(k==sum/L && l==0)
23   {
24     yes=1;
25     return;
26   }
27   if(l==0)
28   {
29     if(k==0)  i=0;
30     else  i=stick[k-1].front()+1;
31     for(;i<n && vis[i];i++);
32     if(i<n && len[i]<=L)
33     {
34       vis[i]=1;
35       stick[k].push_back(i);
36       dfs(k,len[i],L);
37       stick[k].pop_back();
38       vis[i]=0;
39     }
40   }
41   else
42   {
43     for(i=stick[k].back()+1;!yes && i<n;i++)
44     {
45       if(l+len[i]>L || vis[i])  continue;
46       vis[i]=1;
47       stick[k].push_back(i);
48       dfs(k,l+len[i],L);
49       stick[k].pop_back();
50       vis[i]=0;
51       if(l+len[i]==L) break;
52     }
53   }
54 }
55 int main()
56 {
57   int i,max;
58   while(scanf("%d",&n)&&n)
59   {
60     sum=max=0;
61     for(i=0;i<n;i++)
62     {
63       scanf("%d",&len[i]);
64       sum+=len[i];
65       max=MAX(max,len[i]);
66     }
67     qsort(len,n,sizeof(len[0]),cmp);
68     yes=0;
69     for(i=max;i<=sum;i++)
70     {
71       if(sum%i) continue;
72       for(int j=0;j<n;j++)  stick[j].clear();
73       memset(vis,0,sizeof(vis));
74       dfs(0,0,i);
75       if(yes) break;
76     }
77     printf("%d\n",i);
78   }
79   return 0;
80 }

BT数据如下：

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