P1025 [NOIP2001 提高组] 数的划分 题解复盘基本信息项目内容题目编号、来源P1025 洛谷 / [NOIP2001 提高组] 数的划分训练层级B DFS 剪枝知识版块DFS、剪枝、组合枚举解题前・关键信号识别维度分析目标、约束、底层结构目标把整数 n 分成 k 份每份 ≥ 1求方案数顺序无关约束n ≤ 200k ≤ 6底层结构组合枚举 剪枝优化。数据规模n ≤ 200k ≤ 6DFS 剪枝完全可行。候选算法和依据DFS 剪枝依据把问题转化为「从 1~n 中选 k 个可重复的数使和为 n且不下降」这是组合枚举的变种用 start 参数保证不下降。复杂度预判时间复杂度 O(C(nk-1, k))k ≤ 6 剪枝后很小空间复杂度 O(k)。解题后・外化复盘维度内容实现结构 / 核心思路第一步定义dfs(step, start, sum)step 表示已经选了几个数start 表示当前可以从哪个数开始选保证不下降sum 表示当前总和第二步如果step k检查sum n若成立则 ans第三步枚举 i 从 start 到 n用剪枝sum i * (k - step) n跳过不可能的分支第四步递归dfs(step 1, i, sum i)。核心思想把“划分”转化为“选 k 个可重复的数使和为 n且不下降”用 DFS 枚举所有组合剪枝优化。错因回溯1. 把问题想成排列导致重复计算如 1,1,5 和 1,5,1 算成两种2. 没有剪枝导致超时3. 递归出口写成step k从 1 开始和从 0 开始搞混4.start传递错误写成start 1而不是i因为允许重复选同一个数。边界和易错点1. 顺序无关所以要保证不下降start参数2. 同一个数可以选多次所以递归时start传i而不是i13. 剪枝条件sum i * (k - step) n如果从 i 开始后面全取最小值 i 都已经超过 n直接 break4. k 最大 6但 n 最大 200剪枝后很快。下次看到什么信号我应该想到这个方法看到「把 n 分成 k 份 顺序无关 求方案数」DFS 剪枝 或 DP。AC 完整代码#includeiostream#includealgorithm#includeiomanip#includevectorusingnamespacestd;intn,k;intans;voiddfs(intstep,intstart,intsum){if(sumn)return;if(stepk){if(sumn)ans;return;}for(intistart;in;i){if(sumi*(k-step)n)break;dfs(step1,i,sumi);}}intmain(){cinnk;dfs(0,1,0);coutans;return0;}