AcWing 167. 木棒
2021/8/17 23:08:21
本文主要是介绍AcWing 167. 木棒,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剪枝常用策略:
-
优化搜索顺序:可以先搜规模小的分支。
-
排除等效冗余:例如对于一个组合型枚举,\(1,2,3\)与\(2,3,1\)这是一样的,所以可以排除一下。
-
可行性剪枝:搜索过程中及时对状态进行检查,发现分支不符合本意,即提早发现是一个死胡同,就剪掉;
-
最优性剪枝:如果当前代价已经超过了最优解,那么就没必要再搜了。
原题链接:AcWing 167. 木棒
剪枝:
-
优化搜索顺序:将树枝从大到小排序。
-
排除等效冗余:
(1) 那么可以按组合型顺序枚举。
(2) 对于当前拼接失败的小木棍长度,接下来不再拼接与其长度相同的木棍。 -
如果在当前原始木棍中尝试拼接第一根木棍的递归分支失败了,那么就直接返回失败,不再继续搜索,直接回溯。
-
如果在当前原始木棍中拼入最后一根,木棒恰好拼接完整,并且接下来拼接剩余原始木搜索失败,那么直接回溯,解释如下图。
// 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. 木棒的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升