洛谷P1120-小木棍

Problem 洛谷P1120-小木棍

Accept: 3.1k Submit: 20.9k
Time Limit: 1000 mSec Memory Limit : 128MB

Problem Description

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

Input

共二行。

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中

（管理员注：要把超过

第二行为

Output

一个数，表示要求的原始木棍的最小可能长度

Sample Input

9
5 2 1 5 2 1 5 2 1

Sample Output

题目链接：https://www.luogu.org/problemnew/show/P1120

dfs经典题目，关键在于剪枝。

首先给木棒排个序，每次尝试加木棒是都是先加目前能加的最大的，因为如果出现如下情况：

6 = 1+2+3，先用6肯定是优于用1、2、3的，因为小木棒更加灵活。

一共有三个比较重要的剪枝：

1.如果当前剩余长度==L，而该次搜索失败了，就代表着当前那根木棒不可能再和别的木棒一起凑出L，自然要return.

如果left==len[当前]，而该次搜索失败了，就不可能再成功了，因为这个left不用当前的木棒去凑，就一定要用短的去凑，即便用短的凑成功了，也就成了6 = 1+2+3的情况，不会再成功了。

2.如果这根木棒与前一根木棒长度相同，并且前一根搜索失败，那这一根自然不用再搜索了。

3.由于这个题数据加强，因此多了这个剪枝，感觉这个剪枝和Dinic的当前弧优化很类似，就是dfs多了一个参数：该次搜索从哪一根开始，这个具体操作也很简单，肯定是从上一根加进来的木棒的下一根开始，也就是说那些长的木棒就不再试了，因为这种情况再那些长的木棒的搜索过程中已经尝试过并且失败。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 68;
 9 int n,m;
10 int L,len[maxn];
11 bool used[maxn];
12 
13 bool cmp(const int &a,const int &b){
14     return a > b;
15 }
16 
17 bool dfs(int leftm,int sta,int leftl){
18     if(leftm == 0){
19         if(leftl == 0) return true;
20         else return false;
21     }
22     if(leftl == 0) sta=1,leftl = L;
23     for(int i = sta;i <= m;i++){
24         if(len[i] > leftl || used[i]) continue;
25         if(i>1 && !used[i-1] && len[i]==len[i-1]) continue;
26         used[i] = true;
27         if(dfs(leftm-1,i+1,leftl-len[i])) return true;
28         used[i] = false;
29         if(leftl==len[i] || leftl==L) return false;
30     }
31     return false;
32 }
33 
34 int main()
35 {
36     //freopen("input.txt","r",stdin);
37     scanf("%d",&n);
38     m = 0;
39     int x;
40     int sum = 0;
41     for(int i = 0;i < n;i++){
42         scanf("%d",&x);
43         if(x <= 50){
44             len[++m] = x;
45             sum += x;
46         }
47     }
48     sort(len+1,len+1+m,cmp);
49     int Max = len[1];
50     for(L = Max;L <= sum/2;L++){
51         if(sum%L == 0){
52             memset(used,false,sizeof(used));
53             if(dfs(m,1,L)){
54                 printf("%d
",L);
55                 break;
56             }
57         }
58     }
59     if(L > sum/2) printf("%d
",sum);
60     return 0;
61 }