题解：学而思编程 火灾

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：火灾

【题目描述】

小猴的房子着火了，他想从大火中带走价值尽可能多的物品，每次他只能带走一个，救出第i ii个物品需要的时间是t i t_iti​​，价值为p i p_ipi​​。

而第i ii个物品将在起火后d i d_idi​​ 时间后被完全烧掉，这要求救出这个物品的时刻必须严格小于d i d_idi​​。特别的，如果t i ≥ d i t_i≥d_iti​≥di​​，该物品无法被救出。

小猴一个接一个地救出他的物品，救出物品之间的时间忽略不计。问他能救出最多多少价值的物品？

【输入】

第一行为物品总数n nn

接下来n nn行，每行有三个整数t i t_iti​​，p i p_ipi​​，d i d_idi​​

【输出】

输出能带走的最大的价值总和

【输入样例】

3 2 4 7 2 5 6 3 6 7

【输出样例】

11

【核心思想】

1. 问题分析：给定n nn个物品，每个物品救出需要t i t_iti​时间、价值p i p_ipi​，且必须在d i d_idi​时间之前救出（严格小于d i d_idi​）。每次只能救一个物品，求能带走的最大价值总和。这是一个带截止时间的01背包问题。

2. 算法选择：

   • 按截止时间排序：将物品按d i d_idi​升序排序，确保在考虑第i ii个物品时，所有已处理的物品截止时间都不大于它
   • 01背包DP：f [ j ] f[j]f[j]表示在时间j jj内能获得的最大价值
   • 逆序枚举：为保证每个物品只选一次，内层循环逆序枚举时间

3. 关键步骤：

   • 读取输入：n nn（物品数量），每个物品的t i , p i , d i t_i, p_i, d_iti​,pi​,di​
   • 按截止时间排序：sort(a + 1, a + n + 1, cmp)，按d i d_idi​升序
   • 01背包DP（i ii从1 11到n nn）：
     • 逆序枚举时间j jj从a [ i ] . d − 1 a[i].d - 1a[i].d−1到a [ i ] . t a[i].ta[i].t：
       • f [ j ] = max ⁡ ( f [ j ] , f [ j − a [ i ] . t ] + a [ i ] . p ) f[j] = \max(f[j], f[j - a[i].t] + a[i].p)f[j]=max(f[j],f[j−a[i].t]+a[i].p)
     • 注意：j jj的上限是a [ i ] . d − 1 a[i].d - 1a[i].d−1，因为必须在截止时间之前完成
   • 统计答案：遍历所有可能的时间点1 11到a [ n ] . d − 1 a[n].d - 1a[n].d−1，取最大值
   • 输出结果：最大价值总和a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( n × D ) O(n \times D)O(n×D)，其中D = max ⁡ ( d i ) D = \max(d_i)D=max(di​)，排序O ( n log ⁡ n ) O(n \log n)O(nlogn)，背包O ( n × D ) O(n \times D)O(n×D)
   • 空间复杂度：O ( D ) O(D)O(D)，一维DP数组

5. 带截止时间的01背包核心思想：

   • 排序预处理：按截止时间排序后，每个物品的可用时间范围是独立的，不会互相干扰
   • 时间上限限制：对于物品i ii，枚举时间上限为d i − 1 d_i - 1di​−1，确保在截止时间前完成
   • 逆序枚举保证：内层逆序枚举确保每个物品只被选取一次，符合01背包特性
   • 一维数组优化：使用滚动数组将空间复杂度从O ( n × D ) O(n \times D)O(n×D)优化到O ( D ) O(D)O(D)
   • 适用于带时间限制的资源分配、任务调度类问题

【算法标签】

#01背包

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// ================= 常量与全局变量 =================constintN=1005;// 最大物品数量intn;// 物品数量intf[20005];// 动态规划数组，f[j] 表示在时间 j 内能获得的最大价值intans=-1e9;// 最终答案，初始化为极小值// 物品结构体structNode{intt;// 耗时intp;// 价值intd;// 截止时间}a[N];// ================= 按截止时间升序排序 =================boolcmp(Node x,Node y){returnx.d<y.d;}// ================= 主函数 =================intmain(){// 读取物品数量cin>>n;// 读取每个物品的耗时、价值和截止时间for(inti=1;i<=n;i++)cin>>a[i].t>>a[i].p>>a[i].d;// 按截止时间升序排序sort(a+1,a+n+1,cmp);// 01 背包：每个物品只能选一次for(inti=1;i<=n;i++){// 逆序枚举时间，保证每个物品只使用一次// 时间范围：[a[i].t, a[i].d - 1]// 必须在截止时间之前完成，所以最晚结束时间为 a[i].d - 1for(intj=a[i].d-1;j>=a[i].t;j--){f[j]=max(f[j],f[j-a[i].t]+a[i].p);}}// 在所有可能的时间点中取最大值// 最大截止时间为 a[n].d，因此枚举到 a[n].d - 1for(inti=1;i<=a[n].d-1;i++)ans=max(ans,f[i]);// 输出结果cout<<ans<<endl;return0;}

【运行结果】

3 2 4 7 2 5 6 3 6 7 11