解题：洛谷1120 小木棍

题面

这个题剪枝比较多的说=。=

1.记录最长和最短的木棍，限制枚举的上下界

2.记录木棍的总长$tot$，只在其能被枚举的长度整除时搜索

3.从长到短枚举长度(暂时好像没啥用)

4.每次(不是新的一根木棍时)从上次枚举的长度开始枚举(和3组合起来用的)

5.(强剪枝来了)如果是在尝试拼一根新木棍，那么只要没拼出来就拼不出来了(这个时候没有可以回溯的状态)

6.(也是一个强剪枝，和上面的一个道理)如果恰好拼出一根新木棍就拼不出来了，也是一定拼不出来了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int cnt[60];
 6 int n,rd,len,tot,num,maxx,mini=1e9;
 7 bool DFS(int noww,int lenh,int last)
 8 {
 9     if(noww==num) return true;
10     for(int i=last;i>=mini;i--)
11         if(cnt[i]&&lenh+i<=len)
12         {
13             cnt[i]--; int tmp=lenh+i;
14             if(tmp==len) {if(DFS(noww+1,0,maxx)) return true;}
15             else {if(DFS(noww,tmp,i)) return true;} cnt[i]++;
16             if(!lenh||lenh+i==len) return false;
17         }
18     return false;
19 }
20 int main ()
21 {
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++)
24     {
25         scanf("%d",&rd);
26         if(rd<=50)
27         {
28             cnt[rd]++,tot+=rd;
29             maxx=max(maxx,rd);
30             mini=min(mini,rd);
31         }
32     }
33     bool found=false;
34     for(int i=maxx;i<=tot;i++)
35         if(tot%i==0) 
36         {
37             len=i,num=tot/i;
38             if(DFS(0,0,maxx)) 
39             {
40                 printf("%d",i);
41                 found=true; break;
42             }
43         }
44     if(!found) printf("%d",tot);
45     return 0;
46 }

View Code