DFS 剪枝
点击查看代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10;int n;
int w[N];
int sum, len;
bool st[N];bool dfs(int u, int s, int start)
{if (u * len == sum)return true;if (s == len)return dfs(u + 1, 0, 0);// 排除等效冗余 按照组合数枚举for (int i = start; i < n; i ++) {// 可行性剪枝if (st[i] || s + w[i] > len)continue;st[i] = true;if (dfs(u, s + w[i], i + 1))return true;st[i] = false;// 排除等效冗余 放到头尾失败则失败if (!s || s + w[i] == len)return false;// 排除等效冗余 排除掉相同值的元素int j = i;while (j < n && w[j] == w[i])j ++;i = j - 1;}return false;
}void solve()
{while (cin >> n, n) {memset(st, false, sizeof st);sum = 0;for (int i = 0; i < n; i ++) {cin >> w[i];sum += w[i];}// 优化搜索顺序 从大到小排序sort(w, w + n, greater<int>());len = 1;while (true) {// 可行性剪枝if (sum % len == 0 && dfs(0, 0, 0)) {cout << len << endl;break;}len ++;}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}
- 优化搜索顺序
从大到小排序，减少分支的数量 - 可行性剪枝
只有当单个木棒的长度 \(len\) 可以整除总长度 \(sum\) 时，才进行 \(DFS\) - 排除等效冗余
① 按照组合数枚举
② 如果当前木棍加到当前棒中失败，则直接略过后面所有长度等于当前木棍的木棍
③ 如果当前木棍在当前棒的头部失败，则一定失败
证明：假设存在一种方案，将当前木棍放到后续的棒中成功，则通过调整法，先将木棍调整到该木棍所在棒的最前面，再交换两木棒的位置，这样就把木棒调整到如果这句话的位置，出现矛盾
④ 如果当前木棍在当前棒的尾部失败，则一定失败
证明：假设存在一种方案，将当前木棍放到后续的棒中成功，由于木棒的长度都相同，那么即使不把当前木棍拼接到当前木棒，最后当前木棒拼接的长度总和还是等于当前木棍，那么通过把这一段的木棍和当前木棍调整，就会出现矛盾
