P9011 [USACO23JAN] Air Cownditioning II B

记录138

#include<bits/stdc++.h> using namespace std; const int N=110; // 定义常量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 ans=1e9; // 定义全局变量ans，记录满足条件的最少花费，初始化为一个极大值 // 检查当前选中的空调方案是否满足所有奶牛的降温需求 bool check(){ for(int i=1;i<=n;i++){ // 遍历每一头奶牛 // 检查该奶牛占据的每一个牛栏是否都达到了降温需求c[i] for(int j=s[i];j<=t[i];j++){ if(cur[j]<c[i]){ // 如果某个牛栏的降温量不足 return false; // 当前方案不合法，返回false } } } return true; // 所有奶牛的需求都满足，返回true } // 深度优先搜索（DFS）函数，step表示当前正在决策第几台空调，sum表示当前已花费的金钱 void dfs(int step,int sum){ if(step>m){ // 如果已经决策完了所有的m台空调 if(check()) ans=min(ans,sum); // // 当前方案如果合法，更新全局最小花费 return; // 结束当前递归分支 } // 选择1：不选第deep台空调，直接决策下一台，花费不变 dfs(step+1,sum); // 选择2：选第step台空调 for(int i=a[step];i<=b[step];i++){ // 将该空调的降温效果累加到模拟数组中 cur[i]+=p[step]; } dfs(step+1,sum+cost[step]); // 决策下一台空调，花费加上当前空调的费用 // 回溯：撤销选择第step台空调的影响（将降温效果减回去），以免影响其他分支 for(int i=a[step];i<=b[step];i++){ cur[i]-=p[step]; } } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭标准流同步，提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定，加快读取速度 cin>>n>>m; // 读入奶牛数量n和空调数量m for(int i=1;i<=n;i++){ // 循环读入每头奶牛的信息 cin>>s[i]>>t[i]>>c[i]; // 读入左边界、右边界和降温需求 } for(int i=1;i<=m;i++){ // 循环读入每台空调的信息 cin>>a[i]>>b[i]>>p[i]>>cost[i]; // 读入左边界、右边界、降温能力和花费 } dfs(1,0); // 从第1台空调开始搜索，初始花费为0 cout<<ans<<"\n"; // 输出满足所有奶牛需求的最少花费 return 0; // 程序正常结束 }

题目传送门https://www.luogu.com.cn/problem/P9011

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

核心解题思路

这道题是一道非常经典的状态空间搜索（子集枚举）问题。

1. 数据规模分析：
   题目中奶牛数量 N≤20 ，牛栏编号范围 ≤100 ，而最关键的是空调数量M≤10 。由于 MM 非常小，我们可以直接枚举所有空调的选取状态。

2. 算法选择（DFS + 回溯）：
   对于每一台空调，我们只有两种选择：“购买”或“不购买”。因此，总共有 2M 种可能的组合方案。我们可以使用深度优先搜索（DFS）来遍历这棵决策树。

   • 在搜索过程中，我们需要一个数组cur[]来实时记录当前选中的空调组合下，每个牛栏被降低的温度。
   • 当所有空调都决策完毕后，我们检查cur[]数组是否满足所有奶牛的降温需求。如果满足，则更新全局最小花费。
   • 为了不影响其他分支的搜索，在选择某台空调并递归后，必须将其降温效果从cur[]中减去（即回溯操作）。

代码分块详细解释

1. 头文件、常量与全局变量定义

#include<bits/stdc++.h> using namespace std; const int N=110; // 定义常量 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 ans=1e9; // 定义全局变量 ans，记录满足条件的最少花费，初始化为一个极大值

• 详细分析：这部分定义了算法所需的全局状态。cur[N]数组是本题的核心，它充当了一个“虚拟温度计”，用来动态模拟当前决策下各个牛栏的降温情况。ans初始化为1e9（一个比最大可能花费大得多的数），作为打擂法求最小值的初始基准。

2. 合法性检查函数（check）

// 检查当前选中的空调方案是否满足所有奶牛的降温需求 bool check(){ for(int i=1;i<=n;i++){ // 遍历每一头奶牛 // 检查该奶牛占据的每一个牛栏是否都达到了降温需求 c[i] for(int j=s[i];j<=t[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(step>m){ // 如果已经决策完了所有的 m 台空调 if(check()) ans=min(ans,sum); // 当前方案如果合法，更新全局最小花费 return; // 结束当前递归分支 } // 选择 1：不选第 step 台空调，直接决策下一台，花费不变 dfs(step+1, sum); // 选择 2：选第 step 台空调 for(int i=a[step];i<=b[step];i++){ // 将该空调的降温效果累加到模拟数组中 cur[i]+=p[step]; } dfs(step+1, sum+cost[step]); // 决策下一台空调，花费加上当前空调的费用 // 回溯：撤销选择第 step 台空调的影响（将降温效果减回去），以免影响其他分支 for(int i=a[step];i<=b[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); cin>>n>>m; // 读入奶牛数量 n 和空调数量 m for(int i=1;i<=n;i++){ // 循环读入每头奶牛的信息 cin>>s[i]>>t[i]>>c[i]; // 读入左边界、右边界和降温需求 } for(int i=1;i<=m;i++){ // 循环读入每台空调的信息 cin>>a[i]>>b[i]>>p[i]>>cost[i]; // 读入左边界、右边界、降温能力和花费 } dfs(1,0); // 从第 1 台空调开始搜索，初始花费为 0 cout<<ans<<"\n"; // 输出满足所有奶牛需求的最少花费 return 0; }

• 详细分析：主函数负责数据的读入和算法的启动。由于 M 最大为 10，搜索树的节点总数为 2^10=1024 ，加上每次check的复杂度为 O(N×100) ，整体计算量极小，可以在瞬间得出结果。

核心逻辑总结表