记录138#includebits/stdc.h using namespace std; const int N110; // 定义常量N表示牛栏的最大范围题目保证100 int n,m; // n表示奶牛数量m表示空调数量 int s[N],t[N],c[N]; // 记录每头奶牛的左边界s、右边界t和降温需求c int a[N],b[N],p[N],cost[N]; // 记录每台空调的左边界a、右边界b、降温能力p和花费cost int cur[N]; // 模拟数组记录当前选中的空调对每个牛栏的总降温量 int ans1e9; // 定义全局变量ans记录满足条件的最少花费初始化为一个极大值 // 检查当前选中的空调方案是否满足所有奶牛的降温需求 bool check(){ for(int i1;in;i){ // 遍历每一头奶牛 // 检查该奶牛占据的每一个牛栏是否都达到了降温需求c[i] for(int js[i];jt[i];j){ if(cur[j]c[i]){ // 如果某个牛栏的降温量不足 return false; // 当前方案不合法返回false } } } return true; // 所有奶牛的需求都满足返回true } // 深度优先搜索DFS函数step表示当前正在决策第几台空调sum表示当前已花费的金钱 void dfs(int step,int sum){ if(stepm){ // 如果已经决策完了所有的m台空调 if(check()) ansmin(ans,sum); // // 当前方案如果合法更新全局最小花费 return; // 结束当前递归分支 } // 选择1不选第deep台空调直接决策下一台花费不变 dfs(step1,sum); // 选择2选第step台空调 for(int ia[step];ib[step];i){ // 将该空调的降温效果累加到模拟数组中 cur[i]p[step]; } dfs(step1,sumcost[step]); // 决策下一台空调花费加上当前空调的费用 // 回溯撤销选择第step台空调的影响将降温效果减回去以免影响其他分支 for(int ia[step];ib[step];i){ cur[i]-p[step]; } } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定加快读取速度 cinnm; // 读入奶牛数量n和空调数量m for(int i1;in;i){ // 循环读入每头奶牛的信息 cins[i]t[i]c[i]; // 读入左边界、右边界和降温需求 } for(int i1;im;i){ // 循环读入每台空调的信息 cina[i]b[i]p[i]cost[i]; // 读入左边界、右边界、降温能力和花费 } dfs(1,0); // 从第1台空调开始搜索初始花费为0 coutans\n; // 输出满足所有奶牛需求的最少花费 return 0; // 程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P9011前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的状态空间搜索子集枚举问题。数据规模分析题目中奶牛数量 N≤20 牛栏编号范围 ≤100 而最关键的是空调数量M≤10 。由于 MM 非常小我们可以直接枚举所有空调的选取状态。算法选择DFS 回溯对于每一台空调我们只有两种选择“购买”或“不购买”。因此总共有 2M 种可能的组合方案。我们可以使用深度优先搜索DFS来遍历这棵决策树。在搜索过程中我们需要一个数组cur[]来实时记录当前选中的空调组合下每个牛栏被降低的温度。当所有空调都决策完毕后我们检查cur[]数组是否满足所有奶牛的降温需求。如果满足则更新全局最小花费。为了不影响其他分支的搜索在选择某台空调并递归后必须将其降温效果从cur[]中减去即回溯操作。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; const int N110; // 定义常量 N表示牛栏的最大范围题目保证100 int n,m; // n表示奶牛数量m表示空调数量 int s[N],t[N],c[N]; // 记录每头奶牛的左边界s、右边界t和降温需求c int a[N],b[N],p[N],cost[N]; // 记录每台空调的左边界a、右边界b、降温能力p和花费cost int cur[N]; // 模拟数组记录当前选中的空调对每个牛栏的总降温量 int ans1e9; // 定义全局变量 ans记录满足条件的最少花费初始化为一个极大值详细分析这部分定义了算法所需的全局状态。cur[N]数组是本题的核心它充当了一个“虚拟温度计”用来动态模拟当前决策下各个牛栏的降温情况。ans初始化为1e9一个比最大可能花费大得多的数作为打擂法求最小值的初始基准。2. 合法性检查函数check// 检查当前选中的空调方案是否满足所有奶牛的降温需求 bool check(){ for(int i1;in;i){ // 遍历每一头奶牛 // 检查该奶牛占据的每一个牛栏是否都达到了降温需求 c[i] for(int js[i];jt[i];j){ if(cur[j]c[i]){ // 如果某个牛栏的降温量不足 return false; // 当前方案不合法返回 false } } } return true; // 所有奶牛的需求都满足返回 true }详细分析这个函数用于在搜索到达叶子节点即所有空调都决策完毕时判断当前方案是否可行。它遍历每一头奶牛所在的区间 [si,ti][si​,ti​] 逐一比对cur数组中的实际降温量是否大于等于需求 cici​ 。只要有一个牛栏不达标整个方案就作废。3. 核心逻辑DFS 与回溯// 深度优先搜索DFS函数step 表示当前正在决策第几台空调sum 表示当前已花费的金钱 void dfs(int step, int sum){ if(stepm){ // 如果已经决策完了所有的 m 台空调 if(check()) ansmin(ans,sum); // 当前方案如果合法更新全局最小花费 return; // 结束当前递归分支 } // 选择 1不选第 step 台空调直接决策下一台花费不变 dfs(step1, sum); // 选择 2选第 step 台空调 for(int ia[step];ib[step];i){ // 将该空调的降温效果累加到模拟数组中 cur[i]p[step]; } dfs(step1, sumcost[step]); // 决策下一台空调花费加上当前空调的费用 // 回溯撤销选择第 step 台空调的影响将降温效果减回去以免影响其他分支 for(int ia[step];ib[step];i){ cur[i]-p[step]; } }详细分析这是代码的灵魂完美体现了回溯算法的“选择 - 递归 - 撤销选择”三步走策略。递归终止条件当step m时说明 MM 台空调已经全部决策完毕此时调用check()函数进行合法性验证如果合法则更新全局最优解ans。分支 1不买直接递归进入下一台空调的决策当前花费sum和cur数组均保持不变。分支 2购买首先通过循环将第step台空调的降温能力p[step]累加到其覆盖区间 [astep,bstep]的cur数组中然后带着增加的花费sum cost[step]递归进入下一层。回溯操作当“购买”这个分支递归返回后为了不影响后续“不买”分支或其他组合的计算必须将刚才加上的降温效果原封不动地减回去。4. 主函数输入处理与启动搜索int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; // 读入奶牛数量 n 和空调数量 m for(int i1;in;i){ // 循环读入每头奶牛的信息 cins[i]t[i]c[i]; // 读入左边界、右边界和降温需求 } for(int i1;im;i){ // 循环读入每台空调的信息 cina[i]b[i]p[i]cost[i]; // 读入左边界、右边界、降温能力和花费 } dfs(1,0); // 从第 1 台空调开始搜索初始花费为 0 coutans\n; // 输出满足所有奶牛需求的最少花费 return 0; }详细分析主函数负责数据的读入和算法的启动。由于 M 最大为 10搜索树的节点总数为 2^101024 加上每次check的复杂度为 O(N×100) 整体计算量极小可以在瞬间得出结果。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点模拟数组int cur[N]动态记录当前方案下各牛栏的降温量将抽象的空调覆盖重叠问题转化为直观的数组累加操作合法性检查check()函数验证当前方案是否满足所有奶牛需求在搜索树的叶子节点进行“剪枝”或“记录答案”的判定状态累加cur[i] p[step]模拟购买空调后的降温效果在 DFS 向下递归时正确传递当前决策带来的状态改变回溯操作cur[i] - p[step]撤销购买空调带来的状态改变保证 DFS 的不同分支之间互不干扰是回溯算法的核心子集枚举双重dfs递归遍历所有空调的购买组合利用 M≤10M≤10 的小规模用暴力搜索替代复杂的贪心或 DP