[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 剪枝题 ~~

从小到大枚举 [maxLen, sumLen] 上所有 sumLen 的因数,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

常年不在线的QQ:
49750

不定期更新的GitHub:
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