Loading... # ACWing 167 木棒 题解 ## 题目描述 乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过$50$个长度单位。 然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。 请你设计一个程序，帮助乔治计算木棒的可能最小长度。 每一节木棍的长度都用大于零的整数表示。 ## 输入 输入包含多组数据，每组数据包括两行。 第一行是一个不超过$64$的整数，表示砍断之后共有多少节木棍。 第二行是截断以后，所得到的各节木棍的长度。 在最后一组数据之后，是一个零。 ## 输出 为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。 ## 解题思路 本题可以用dfs的方式解决 考虑到对于每一个空位都有九种可能， 假设空位个数为$n$， 则一共的搜索次数为$9^n$， 因此一定需要考虑剪枝操作 - 优化搜索顺序 - 优化搜索顺序， 优先搜索分支数量较少的节点 - 对于本题而言， 可以对输入的木棍长度按照**从大到小排序**， 然后从大到小依次枚举组合， 从而减少搜索的分支数量 - 排除等效冗余 - 去掉重复的情况， 防止重复搜索 - 在本题中， 为了排除等效冗余， 需要枚举组合情况而不是排列， 每次枚举一个组 - 可行性剪枝 - 当当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回。 - 在本题中具有以下几种可行性剪枝： - 木棒的长度只能是所有木棍的总长`sum`的一个约数， 并且木棒的长度一定大于等于最长的木棍 - 设当前枚举到第$k$根木棍， 并且选择第$k$根木棍的情况向后搜索失败， 则所有满足`i > k && a[i] == a[k]`的木棍都无法分到该组 - 设当前木棍`k`是该木棒的第一根木棍， 且当前搜索失败， 则一定没有解决方案 - 证明：设当前木棍`k`是第`i`个木棒的第一根木棍， 并且搜索失败， 但是在第`j`个木棒搜索成功， 交换第`i`根木棒和第`j`根木棒， 并改变木棍的位置， 令木棍`k`为第一根木棍， 此时搜索成功， 与原命题矛盾 - 同理有，当前木棍`k`是该木棒的最后一根木棍， 且当前搜索失败， 则一定没有解决方案 - 最优性剪枝 - 当搜到一半的时候，已经劣于之前搜到的答案，那么这个方案肯定是不行的，即刻停止搜索，进行回溯。 - 本题中没有进行最优性剪枝， 或者说由于只需要输出最短的木棒长度， 因此在第一次成功搜索后返回即为最优性剪枝 - 记忆化搜索 - 即动态规划中的记忆化搜索 - 本题中没有使用记忆化搜索 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <algorithm> #define endl '\n' using namespace std; const int N = 2e5 + 10; int n; int a[N]; int cnt[N]; bool st[N]; int sum; bool dfs(int i, int weight, int start, int len) { if(i * len == sum) return true; if(weight == len) return dfs(i + 1, 0, 1, len); for(int j = 1; j <= n; j ++) { if(st[j] || weight + a[j] > len) continue; st[j] = true; if(dfs(i, weight + a[j], j + 1, len)) return true; st[j] = false; if(weight == 0 || weight + a[j] == len) return false; int k = j + 1; while(k < n && a[k] == a[j]) k ++; j = k - 1; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin >> n) { if(n == 0) break; memset(cnt, 0, sizeof cnt); memset(st, 0, sizeof st); sum = 0; for(int i = 1; i <= n; i ++) { cin >> a[i]; sum += a[i]; } sort(a + 1, a + 1 + n, greater<int>()); for(int i = a[1]; i <= sum; i ++) { if(sum % i) continue; if(dfs(0, 0, 1, i)) { cout << i << endl; break; } } } return 0; } ``` 最后修改：2025 年 03 月 07 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏