[POJ 1011] Sticks【DFS】
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 剪枝题 ~~
从小到大枚举 [maxLen, sumLen] 上所有 sumLen 的因数，DFS 找到第一个可以拼出的长度值即可。
DFS 时尝试拼接若干根目标长度的木棍，参数仅需保存当前正在拼接的木棍长度即可（之前的木棍长度均为目标值）。
剪枝策略，缺一不可：
- 最优性剪枝：DFS 从大到小尝试，且当前木棒一定不比之前的木棒长，避免重复搜索。
- 可行性剪枝#1：如果当前木棒不可行，则相同长度的木棒均可跳过。
- 可行性剪枝#2：如果当前木棒是本次拼接的第一根，且不可行，则用更短的木棒替换一定不会更优。
- 可行性剪枝#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;
}
发表评论