poj1011 && uva307 DFS + 剪枝

将木棒从大到小排列，保证每次的选择都是最长可选的木棒。

剪枝：

1 . 如果第 i 根木棒被选择却无法成功拼接，那么后面与其长度相同的也不能选择。

2 . 如果第 cnt + 1 根木棒无法成功拼接，就应该立即重构第 cnt 根木棒。那么如何判断是否能构造木棍呢？每次可以选择的最长木棒必须要选择，因为就算这次不选择，后面木棒的拼接也要用到该木棒，如果不能利用该木棍直接返回构造上一根木棍。

3 . 如果现在加入长度为x的一节木棒刚好组成一节完整的木棒，但是后面的木棍不能成功拼接，就重新选取上一节木棍，改变最后需要的长度x。

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100;

int len[maxn], vis[maxn], n;
bool cmp(int a, int b){
	return a > b;
}

int Len, Cnt; //长度和数量 

bool dfs(int cnt, int cur, int lenth){
	if(cnt == Cnt) return true;
	for(int i = cur; i < n; ++i){
		if(vis[i] || lenth + len[i] > Len) continue;
		if(lenth + len[i] < Len){
			vis[i] = 1;
			if(dfs(cnt, i + 1, lenth + len[i])) return true;
			vis[i] = 0;
			if(lenth == 0) return false;
			while(len[i + 1] == len[i] && i < n) ++i; //len[i]没有被选择
		}
		else if(lenth + len[i] == Len){ //拼成1根
			vis[i] = 1;
			if(dfs(cnt + 1, 0, 0)) return true;
			vis[i] = 0;
			return false;
		}
	}
	return false;
}

int main(){
	while(scanf("%d", &n) == 1 && n){
		memset(vis, 0, sizeof(vis));
		int sum = 0;
		for(int i = 0; i < n; ++i){
			scanf("%d", &len[i]);
			sum += len[i];
		}
		sort(len, len + n, cmp); //根据长度降序排序 

		for(Len = len[0]; Len <= sum; ++Len){
			if(sum % Len) continue;
			Cnt = sum / Len;
			if(dfs(0, 0, 0)) {
				printf("%d\n", Len);
				break;
			}
		}
	}
	return 0;
}

如有不当之处欢迎指出！

巴特西

poj1011 && uva307 DFS + 剪枝

最新文章

热门文章