1. 先搞懂题目本身被砍断的木棍和等长原木棍UVA-307小木棍Sticks在《算法竞赛入门经典第2版》的暴力求解法章节里几乎是每位刷题人都会撞上的一道题。我当初第一次写这题的题解答案代码用的就是教科书里那种裸回溯把小木棍按顺序试进每一根原始木棍不行就还原再试。运行结果很稳定TLE。后来我把各种剪枝一条条加上去才真正理解这题为什么能当成DFS算法的“分水岭”。这篇博文从题目描述开始把搜索流程、每条剪枝的证明、完整AC代码和实际踩坑都讲清楚适合正在啃紫书、或者已经写过代码但不知道剪枝为什么有效的读者。1.1 题目到底在说什么原题名叫Sticks。简单说George原本有一些长度相同的木棍他把它们随机砍成了若干小段每段长度都不超过50。现在他手里只有这些小段忘了自己原来有几根木棍、每根多长。题目会给出小段的个数和每段长度要求你算出原始状态下单根木棍的最小可能长度。这里有几个隐含前提原始的木棍根数不定但每一根长度相等记为L。所有小段的总长度sum是不变的所以sum必须能被L整除。每根小段的长度都不可能超过L也就是L 全部小段中的最大值。小段之间的拼接没有损耗长度直接相加。输入是多组数据每组第一行是一个整数n表示小段数量第二行是n个整数表示每段长度。n 0表示输入结束。对每组数据输出一个整数就是最小可能的原始木棍长度。1.2 把样例手算一遍题目给的经典样例是第一组9 5 2 1 5 2 1 5 2 1总长度sum 24最大小段是5。能整除24的候选长度有6、8、12、24。我们从最小的开始试L 6三根长度为5的小段各配一根长度为1的小段三根长度为2的小段自己合成一根6。能拼成4根原始木棍所以答案是6。第二组4 1 2 3 4sum 10最大小段是4。候选长度是5和10。L 5时可以拼出4 1和3 2两根所以答案是5。这个样例值得记一下最大小段是4但4不能作为答案因为10不被4整除。光想着“从最大值开始猜”是没用的必须先从数学上把候选长度约束住。1.3 最小候选长度的两个硬性条件根据上面的分析任意候选长度L必须同时满足L max(a[i])这是物理约束小段不可能比原木棍还长。sum % L 0这是总量约束所有小段长度加起来必须正好是整数根。所以真正的枚举区间不是1到sum而是[max(a), sum]这个范围内所有能整除sum的数。这个范围已经小很多了但在程序里仍然需要用搜索去判断某一个L到底行不行。后面所有功夫都是围绕“给定一个L怎么快速判断它是否可行”展开的。2. 朴素DFS为什么必挂先看搜索树的规模很多新手会把这道题当成普通的回溯题写一个非常直观的DFS。我要先泼一盆冷水这个方案放在n10还能跑放在n64就必挂。2.1 最直接的搜索状态长什么样朴素写法大概是这样的维护一个“当前正在拼的原始木棍”的已拼长度cur以及已经拼好的原始木棍数量done。每次选一根没用过的小木棍如果cur a[i] L就放进去递归继续如果cur a[i] L相当于拼完一根done加1cur归零。递归入口是cur 0done 0目标是把所有小木棍用完且done sum / L。伪代码大致是bool dfs(int cur, int done) { if (done sum / L) return true; for (int i 0; i n; i) { if (used[i]) continue; if (cur a[i] L) continue; used[i] true; if (dfs(cur a[i], done (cur a[i] L))) return true; used[i] false; } return false; }这段代码逻辑没错但什么都剪不掉。2.2 复杂度到底有多离谱这个问题的本质是把n根不同的小木棍划分成若干组要求每组长度都等于L。这等价于“等和集合划分”是一个NP完全问题。n 64的时候所有可能划分的数量早就是天文数字。具体到朴素DFS递归树的每一层都要考虑“当前这根小木棍放进哪个位置”。哪怕我们限制当前只拼一根原始木棍也要尝试大量组合。一个简单的估算如果只考虑把所有小木棍分成两组可能的划分数量是2的64次方量级分成更多组划分数量只会更多。没有有效剪枝时搜索必然指数爆炸。2.3 朴素搜索浪费在哪里朴素DFS最大的浪费是“把排列当成组合”。举个例子一根原始木棍由1、4、5三根小段组成无论先放1、再放4、最后放5还是先放5、再放4、最后放1在问题里都是同一回事。但裸回溯会把每种放置顺序都当成新分支搜一遍。只要这个小细节不解决同样的分组方案就会被重复搜索很多次。所以第一步优化思路很明确对同一根原始木棍要求小木棍按下标递增使用不要回头。这样一根木棍内部的排列顺序就被固定了。后面在完整代码里这个约束是通过DFS参数idx实现的。3. 核心剪枝策略逐条拆解每条都要知道它为什么有效这道题之所以经典是因为它把这些“效率优化”里的每一个都变成了“逻辑必然”。不是碰运气式的提速而是你能证明某条路根本不可能有解。3.1 降序排列让长木棍先被消耗把a数组按从大到小排序这件事有两个作用。第一个作用很直观当前原始木棍还剩下rest的长度我们要选一根长度小于等于rest的小木棍。如果先处理长木棍可选范围会明显变小分支数量直接减少。第二个作用更隐蔽长木棍越早放下去剩余空间越容易变成“刚好能被某根木棍填满”的状态这能触发后面说的最狠的剪枝。如果你从小到大排序前面全是短棍组合方式太多搜索树又肥又深。3.2 跳过等长小木棍等价方案只搜一次排序之后长度相同的木棍会排在一起。假设我刚刚尝试了把一根长度为5的木棍放进某个位置结果后续递归失败回溯到这里。那么我再尝试下一根长度也是5的木棍放在同一个位置结果会完全一样因为这两根木棍在问题里没有区别。代码里有两种等价写法。第一种是在失败后直接跳过while (i 1 n a[i 1] a[i]) i;第二种是在进入循环时做前置判断if (i 0 a[i] a[i - 1] !used[i - 1]) continue;第二种写法的意思是前一根长度相同的木棍在当前搜索路径上刚刚失败并且已经被回溯释放used恢复成false那当前这根也不用试了。两种写法选一种就行我下面的完整代码用的是第二种加第三种注释里会说明。3.3 新开一根原始木棍时第一段失败直接整体返回这是这条题目里最关键、也最容易被忽略的剪枝。先说触发条件当rest L时说明现在正在开始拼一根全新的原始木棍。假设我选择了某根未使用的小木棍x作为这根木棍的第一段放进之后继续递归最终失败。这时候不用再去试别的木棍作为第一段直接return false。原因可以用反证法想清楚。如果存在一个成功的完整方案x一定在某根原始木棍里。同一根原始木棍里面小段的排列顺序是可以任意调整的那我一定能把x调整到那根木棍的第一位。既然当前状态rest L说明前面的木棍都已经拼完正在开始拼下一根那我完全可以把包含x的那根木棍整体挪到当前这根的位置。所以只要方案能成功就必然存在一个“以x开头”的成功搜索路径。现在这条路径失败了说明不存在这样的方案。于是整个递归直接返回false不需要再试别的第一段。这个剪枝在代码里的位置是在一次失败尝试之后if (rest L) return false;3.4 当前小棍刚好填满剩余空间时失败也直接返回第二个全局剪枝的触发条件是rest a[i]也就是当前这根小木棍的长度正好等于当前原始木棍还需要的长度。选择它之后当前这根原始木棍刚好被填满。如果继续递归失败同样直接return false不用再尝试用其他组合来填满当前木棍。这个剪枝的正确性需要一点交换论证。假设存在一个可行方案但方案里x没有被用来单独填满当前这根而是被放到了后面的某一根原始木棍G里当前这根木棍的剩余部分由另外一些小木棍H填满。由于H的总长度等于rest而rest又等于x的长度那么H的总长度也等于x。现在做一次交换让x单独填满当前木棍把H整体放进原来G的位置。G原来的总长度是L去掉x之后变成L - x再加入总长度为x的H又变回L。其他木棍不受影响。所以只要存在可行方案就一定存在“x单独填满当前木棍”的可行方案。那如果这一次尝试仍然失败就说明当前剩余集合根本不可能完成任务直接返回false。这个交换论证是很多博客不讲的细节但理解了它你才能真正相信这个剪枝不是玄学。3.5 五个剪枝的优先级和组合效果把上面几条整理一下剪枝名称触发位置消灭的分支类型降序排序预处理长木棍晚放产生的冗余排列下标递增dfs的idx参数同一根棍内不同排列等长去重失败回溯后相同长度木棍互换的等价方案第一段失败rest L时递归失败以该木棍开头的所有方案刚好填满失败rest a[i]时递归失败换一组小棍填满当前木棍的所有方案实际调试时我建议先只加降序和下表递增跑一次看TLE再加等长去重最后加两个全局剪枝。这样你能清晰感受到每个剪枝带来的变化而不是一次全加进去出了问题都不知道是哪一条把正确路径也剪掉了。4. 完整C答案代码与逐段注释下面是我最终提交到UVA上能AC的版本配合注释逐段解释。#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 64; int n, sum, L; int a[MAXN]; bool used[MAXN]; // idx: 当前这根原始木棍内继续搜索的起始下标 // rest: 当前这根原始木棍还需要的长度 // cnt: 还需要拼好的原始木棍数量包含当前正在拼的这根 bool dfs(int idx, int rest, int cnt) { if (cnt 0) return true; if (rest 0) { // 当前这根已经拼完开始拼下一根重新从头搜索 return dfs(0, L, cnt - 1); } for (int i idx; i n; i) { if (used[i] || a[i] rest) continue; // 前一根长度相同的木棍刚刚失败并被回溯释放 // 当前这根放在相同位置也会失败跳过。 if (i 0 a[i] a[i - 1] !used[i - 1]) continue; used[i] true; if (dfs(i 1, rest - a[i], cnt)) return true; used[i] false; // 剪枝1: 正在开始一根新木棍第一段选择 a[i] 失败 整体无解 if (rest L) return false; // 剪枝2: a[i] 刚好能填满当前木棍后续仍失败 整体无解 if (rest a[i]) return false; // 等长去重跳过后面所有长度相同的木棍 while (i 1 n a[i 1] a[i]) i; } return false; } int main() { while (scanf(%d, n) 1 n) { sum 0; for (int i 0; i n; i) { scanf(%d, a[i]); sum a[i]; } sort(a, a n, greaterint()); bool found false; for (L a[0]; L sum / 2; L) { if (sum % L ! 0) continue; memset(used, 0, sizeof(used)); if (dfs(0, L, sum / L)) { printf(%d\n, L); found true; break; } } if (!found) printf(%d\n, sum); } return 0; }4.1 为什么枚举到sum / 2就够了很多人会写成for (L a[0]; L sum; L)其实没必要。如果L sum / 2整数除法下sum / L只能等于1也就是所有小木棍拼成一根原始木棍。这组方案必然可行直接就是答案sum。所以真正需要搜索验证的区间最多到sum / 2。如果在这个区间里没有任何可行的L说明答案就是sum直接输出。这里要注意枚举时仍然要满足sum % L 0。因为要拼出至少两根等长的原始木棍总数必须被L整除。4.2 dfs的cnt参数到底在维护什么初始调用时我们要拼的原始木棍根数是sum / L所以调用dfs(0, L, sum / L)。括号里的第三个参数的意思是“包括当前这根在内还差多少根没拼好”。一旦rest变成0说明当前这根完成于是进入下一根并让cnt减1当cnt减到0所有原始木棍都拼完了返回true。为什么rest 0时要重新从0开始搜因为上一根木棍的内部顺序约束对下一根完全不适用下一根是一张白纸所有未使用的小木棍都可以重新参与选择。4.3 最容易写错的三个地方第一个是memset的位置。每次换一个新的候选Lused数组都要被清空。有人把memset放在读入之后、枚举之前那第二个L开始就会带着上一轮的使用标记。第二个是剪枝1和剪枝2的位置。它们必须放在used[i] false之后不能放在递归调用之前。因为这两个剪枝判断的是“我已经尝试把a[i]放进去并且失败了”这个事实而不是“我准备放a[i]”。第三个是回溯时的正确性。递归完成后要立刻used[i] false否则后面的等长判断和循环都会受影响。5. 实测数据与调参记录我在UVA上踩过的坑代码只是最后的结果真正值钱的是调试过程中积累的那些边界情况。这节把我自己踩过的坑和测试用例整理一下。5.1 必须手算的边界用例我建议你至少测下面这几类输入9 5 2 1 5 2 1 5 2 1答案6。4 1 2 3 4答案5。1 10n1只有一根小段那它本身就是一根原始木棍答案10。这里循环L从10到sum/25不会进入直接走最后输出10。如果你把枚举上界写成sum也会得到10两种都对。4 1 1 1 1全部长度相等每根小段都能单独作为原始木棍答案1。8 1 1 1 1 2 2 2 2sum12最大小段是2候选L2可行答案是2。5.2 剪枝顺序对性能的影响真的很大我在本地做了一组随机压力测试n64每段长度在1到50之间随机。完整剪枝的版本递归调用次数只有几千次。但只把剪枝1rest L时直接return false去掉调用次数直接涨到几十万量级如果数据再刁钻一点就是TLE和AC的区别。另一个印象深刻的点是如果你把剪枝2也去掉哪怕还有降序和等长去重很多看似普通的数据都要跑很久。这说明了两个全局剪枝为什么是“核心中的核心”。它们不是锦上添花而是把指数级搜索直接压成了近似的贪心回溯。5.3 UVA评测的几个实际细节我提交时踩过的一个坑是scanf返回值。多组数据要以n0结束写while (scanf(%d, n) 1 n)是最稳的。如果只写while(scanf(%d, n) ! EOF)你会在读入最后一个0时又进入一次循环然后sum变成0程序可能输出奇怪的东西。另外UVA对每组输出就是一行整数不要多打印空行。之前为了美观在每次输出后加了换行第一个换行没问题但最后一组数据后面加不加都无所谓只要别在两组之间多打空行就行。数组大小开到64就够但实际写题我习惯多留几格用const int MAXN 70也不会出错。6. 从紫书视角延伸这类DFS剪枝题还能怎么练如果你是为了刷《算法竞赛入门经典第2版》才做这题做完之后别急着走。把UVA-307抽象出来的模型记住它会在很多地方再次出现。6.1 把UVA-307看成“等和子集划分”这题的本质是给一个集合问能不能把它划分成sum / L个子集使每个子集的和都等于L。这是一个很经典的组合搜索问题名字叫等和子集划分。只要看到这种问题前两个反射动作应该固定下来先排序而且是降序。搜索状态里维护“当前组还差多少”和“下一根从哪个下标开始试”。这两个动作我已经在上面详细解释过可以无脑套用。套用完之后再根据题目条件补充针对性的剪枝。6.2 哪些题和UVA-307是同一套思路洛谷的P1120小木棍数据加强版基本就是UVA-307的兄弟题数据范围更大、卡得更狠很适合用来检验自己对剪枝的理解。LeetCode上也有类似的698题“划分为k个相等的子集”数据规模不算大但剪枝思路完全相通。我做这些题时的体会是不要死记硬背某一条剪枝的写法要记住“哪一类失败信息是全局性的”。比如第一段失败代表整体无解这个结论在很多等和划分题里都能直接搬。只要想明白了这一点换题只是换个包装。6.3 怎么验证自己真的懂了一个很笨但有效的方法把完整代码里的每条剪枝分别注释掉各自跑同一组数据并在dfs入口加一个全局计数器记录函数调用次数。你会看到这些数字的变化比任何讲解都直观。比如我刚才说的那组随机数据完整版本几千次调用去掉剪枝1调用次数暴涨去掉剪枝2很多数据直接跑不完。把这些数字记录下来自己心里就建立起一套“剪枝贡献”的直觉了。以后再碰到新的搜索题你就不只是照着题解抄代码而是能自己判断“这个剪枝非加不可”。我个人到现在还会偶尔翻出UVA-307的代码看一眼。当年AC的那一刻其实没有多大惊喜因为前后改了十几次才跑通但后来几乎所有DFS剪枝题的顺畅感都要归功于这道题逼我把“为什么剪”想明白了。刷题这事最怕的不是写得慢而是没想清楚就急着交UVA-307正好能治这个毛病。