P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins 题解复盘基本信息项目内容题目编号、来源P1460 洛谷 / [USACO2.1] 健康的荷斯坦奶牛训练层级B DFS 回溯知识版块DFS、枚举、回溯、剪枝、字典序解题前・关键信号识别维度分析目标、约束、底层结构目标从 g 种饲料中选出最少的种类使维他命总量满足牛的需求若有多个解输出字典序最小的约束v ≤ 25g ≤ 15底层结构每种饲料只有「选」和「不选」两种状态总方案数 2^g ≤ 32768。数据规模g ≤ 152^15 32768DFS 枚举所有方案完全可行。候选算法和依据DFS 回溯依据g 极小每种饲料选/不选构成一棵深度为 g 的二叉树直接 DFS 枚举所有组合取满足条件的最优方案。复杂度预判时间复杂度 O(2^g × v)g ≤ 15完全可行空间复杂度 O(v g)。解题后・外化复盘维度内容实现结构 / 核心思路第一步读入 v 种维他命的需求量 need[]第二步读入 g 种饲料每种饲料含 v 种维他命存入vita[i][j]第三步 DFS 枚举每种饲料分支1不选分支2选选时累加维他命到 exist[]将编号加入 chosen 集合递归回来要撤销第四步所有饲料处理完后用 check() 检查 exist[] 是否全部 ≥ need[]若满足则与当前最优解比较种数更少 或 种数相同字典序更小更新最优解第五步输出最优解的种数和编号。核心思想g ≤ 15 意味着可以枚举所有方案DFS 是枚举所有「选/不选」组合的标准工具。错因回溯1. 剪枝条件写成 bestcnt导致种数相同的方案被错误剪枝无法更新字典序更小的解2. 输出编号时忘了加空格导致格式错误3.exist数组累加和回溯时下标范围不一致导致数据错乱4. 第一次找到方案时s为空比较条件需要单独处理。边界和易错点1. 剪枝条件用而非保留种数相同的方案继续搜索字典序更小的解2. 回溯时chosen.erase()要在exist恢复之后执行顺序不要搞反3. 输出格式先输出种数再输出每个编号编号间用空格分隔4. 字典序比较编号小的集合字典序更小5.vita数组用vectorint存储下标从 0 开始。下次看到什么信号我应该想到这个方法看到「g ≤ 15 每样东西选/不选 求最优 字典序最小」直接上 DFS 枚举 回溯。AC 完整代码#includeiostream#includealgorithm#includeset#includevectorusingnamespacestd;intv,g,p;intneed[30];intexist[30];setints;vectorintvita[20];intbestcnt1e9;boolcheck(){for(inti0;iv;i){if(exist[i]need[i])returnfalse;}returntrue;}boolsmaller(constsetinta,constsetintb){if(a.size()!b.size())returna.size()b.size();autoit1a.begin(),it2b.begin();while(it1!a.end()){if(*it1!*it2)return*it1*it2;it1;it2;}returnfalse;}voiddfs(intstep,setintchosen){if((int)chosen.size()bestcnt)return;if(stepg){if(check()){if(s.empty()||chosen.size()s.size()||(chosen.size()s.size()smaller(chosen,s))){schosen;bestcntchosen.size();}}return;}dfs(step1,chosen);for(inti0;iv;i){exist[i]vita[step][i];}chosen.insert(step1);dfs(step1,chosen);for(inti0;iv;i){exist[i]-vita[step][i];}chosen.erase(step1);}intmain(){cinv;for(inti0;iv;i){cinneed[i];}cing;for(inti0;ig;i){for(intj0;jv;j){inta;cina;vita[i].push_back(a);}}setintchosen;dfs(0,chosen);couts.size();for(autox:s){cout x;}return0;}