# [POJ 1011] Sticks【DFS】

• 2018-01-01
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory Limit: 10000K

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```

Source

Central Europe 1995

## Solution:

~~ 经典 DFS 剪枝题 ~~

DFS 时尝试拼接若干根目标长度的木棍，参数仅需保存当前正在拼接的木棍长度即可（之前的木棍长度均为目标值）。

1. 最优性剪枝：DFS 从大到小尝试，且当前木棒一定不比之前的木棒长，避免重复搜索。
2. 可行性剪枝#1：如果当前木棒不可行，则相同长度的木棒均可跳过
3. 可行性剪枝#2：如果当前木棒是本次拼接的第一根，且不可行，则用更短的木棒替换一定不会更优。
4. 可行性剪枝#3：如果当前木棒是本次拼接的最后一根，且不可行，则用更短的木棒替换也一定不会更优。

## code: O(玄学) [164K, 16MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int n, a[70], sumlen, dest, fin;
bool vis[70];

inline bool DFS(int upRange, int curlen){  // Guarantee not to search repeatedly, record current connection of sticks
if(fin == n && !curlen) return 1;
for(register int i = upRange; i > 0; i--){
if(vis[i] || curlen + a[i] > dest) continue;
vis[i] = 1, fin++;
bool isSuccessful = (curlen + a[i] == dest) ? DFS(n, 0) : DFS(i - 1, curlen + a[i]);
if(isSuccessful) return 1;
vis[i] = 0, fin--;
if(curlen == 0) return 0;  // No need to search further if it's the first stick of current connection
if(curlen + a[i] == dest) return 0;  // No need to search further if it's the last stick of current connection
while(i > 1 && a[i - 1] == a[i]) i--;  // Skip the sticks of the same length
}
return 0;
}

int main(){
while(scanf("%d", &n) != EOF && n){
sumlen = 0;
for(register int i = 1; i <= n; i++) scanf("%d", a + i), sumlen += a[i];
sort(a + 1, a + n + 1);
for(register int i = a[n]; i <= sumlen; i++){
if(sumlen % i) continue;  // Less than 35 factors in this region
dest = i, memset(vis, 0, sizeof(vis)), fin = 0;
if(DFS(n, 0)){
printf("%d\n", i);
break;
}
}
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai