UVa 307 Sticks 木棍拼接 ID 迭代加深搜

题目链接：Sticks
题目描述：

小明一开始有一些长度相等的木棍，小明现在将木棍砍成了一些长度为整数的木棍，他现在忘记了最开始木棍的长度，你需要找到最短的可能木棍长度，例如给定$5,2,1,5,2,1,5,2,1$那么这些木棍可以是由一根长度为$24$的木棍砍出来的，但是也可以是两根长度为$12$的木棍砍出来，也可以是三根长度为$8$的木棍看出，也可以是$4$根长度为$6$的木棍砍出来。其中$6$是长度最短的，你需要输出$6$。

题解：

由于本题的初始有几根木棍我们并不确定，我们实际上可以倒序枚举初始的木棍数量（从$n$开始，因为初始木棍的数量越多，木棍的长度也短），然后依次搜索所有情况，这就是一个倒序的$ID$算法（通常$ID$都是正着枚举）。
本题的难点在于如何进行搜索。枚举了初始的木棍数量之后，我们就知道了初始的每一根木棍的长度，也就是木棍的长度和除以初始木棍的数量，我们可以将木棍的长度进行排序，我们每次选择木棍进行组合的时候，我们优先处理长度更长的木棍，尝试将其拼接在当前的木棍上，如果长度大于了初始木棍的长度我们可以继续选择稍小的木棍进行处理，如果刚好等于初始木棍的长度，那么我们一定是选择其与当前的木棍进行组合，而不是选择几根更短的木棍进行组合，这是因为如果选择几根更短的木棍，那么剩余木棍的灵活性就会降低，而我们选择这一根木棍进行组合，剩下的木棍有着更多的组合可能性，这也就表明了如果选择一根进行拼接刚好等于初始长度的时候，如果搜索失败即使选择更短的木棍也会搜索失败。

代码：

#include <bits/stdc++.h>using namespace std;int n, maxDepth, sum;
vector<int> len;
bool *used;bool dfs(int nowDepth, int nowLen, int pos)
{if (nowDepth == maxDepth) { return true; }for (int i = pos; i >= 0; i--) {if (used[i]) { continue; }if (nowLen + len[i] < sum / maxDepth) {used[i] = true;if (dfs(nowDepth, nowLen + len[i], i - 1)) { return true; }used[i] = false;while (i - 1 >= 0 && len[i - 1] == len[i]) { i--; } // 相同长度此时一定会失败} else if (nowLen + len[i] == sum / maxDepth) {used[i] = true;if (dfs(nowDepth + 1, 0, n - 1)) { return true; }used[i] = false;return false; // 没有必要选择更短的，因为灵活性更低了}if (nowLen == 0) { return false; } // 这里是为了防止重复搜索}return false;
}int main()
{while (cin >> n && n != 0) {len.resize(n);used = new bool[n]; // 这题没有告知数据范围，所以这里采用了动态内存分配sum = 0;for (int i = 0; i < n; i++) {cin >> len[i];sum += len[i];}sort(len.begin(), len.end());for (maxDepth = n; ;maxDepth--) {if (sum % maxDepth != 0 || len[n - 1] > sum / maxDepth) { continue; }memset(used, 0, sizeof(bool) * n);if (dfs(0, 0, n - 1)) { break; }}cout << sum / maxDepth << endl;delete used;}return 0;
}