C/C++教程

AcWing 167. 木棒

本文主要是介绍AcWing 167. 木棒,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

剪枝常用策略:

  1. 优化搜索顺序:可以先搜规模小的分支。

  2. 排除等效冗余:例如对于一个组合型枚举,\(1,2,3\)与\(2,3,1\)这是一样的,所以可以排除一下。

  3. 可行性剪枝:搜索过程中及时对状态进行检查,发现分支不符合本意,即提早发现是一个死胡同,就剪掉;

  4. 最优性剪枝:如果当前代价已经超过了最优解,那么就没必要再搜了。

原题链接:AcWing 167. 木棒

剪枝:

  1. 优化搜索顺序:将树枝从大到小排序。

  2. 排除等效冗余:
    (1) 那么可以按组合型顺序枚举。
    (2) 对于当前拼接失败的小木棍长度,接下来不再拼接与其长度相同的木棍。

  3. 如果在当前原始木棍中尝试拼接第一根木棍的递归分支失败了,那么就直接返回失败,不再继续搜索,直接回溯。

  4. 如果在当前原始木棍中拼入最后一根,木棒恰好拼接完整,并且接下来拼接剩余原始木搜索失败,那么直接回溯,解释如下图。

1.png

// Problem: 木棒
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/169/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int N = 70;
int w[N];
bool st[N];
int n, cnt, len;

//stick:第几根木棒
//curlen:当前被拼接木棒已经拼接的长度
//last:使用的上一根木棒的下标
bool dfs(int stick, int curlen, int last) {
    //所有木棒拼接好
	if (stick > cnt) return true;
	//第stick根木棒拼接完毕,拼接下一根
	if (curlen == len) return dfs(stick + 1, 0, 1);
	
	int fail = 0;
	for (int i = last; i <= n; i++) {
		if (st[i]) continue;
		if (w[i] == fail) continue; //剪枝2.2:对于当前拼接失败的小木棍长度,接下来不再拼接与其长度相同的木棍。
		if (curlen + w[i] > len) continue; //可行性剪枝
		
		st[i] = true;
		if(dfs(stick, curlen + w[i], i + 1)) return true;
		st[i] = false;
		
		//如果拼接失败
		fail = w[i]; //记录本次用的失败的小木棒
		if (curlen == 0 || curlen + w[i] == len) return false; //剪枝:3,4
	}
	
	return false;
}

int main() {
	while (cin >> n, n) {
		int maxv = 0, sum = 0;
		for (int i = 1; i <= n; i++) {
			cin >> w[i];
			sum += w[i];
			maxv = max(maxv, w[i]);
		}
		
		sort(w + 1, w + n + 1, [&](int a, int b) {
			return a > b;
		});
		
		for (len = maxv; len <= sum; len++) {
			memset(st, false, sizeof st);
			if (sum % len) continue;
			cnt = sum / len;
			if (dfs(1, 0, 1)) break;
		}
		
		cout << len << endl;
	}
    return 0;
}

		

这篇关于AcWing 167. 木棒的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!