本文分享的必刷题目是从蓝桥云课、洛谷、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_itip i p_ipid i d_idi【输出】输出能带走的最大的价值总和【输入样例】3 2 4 7 2 5 6 3 6 7【输出样例】11【核心思想】问题分析给定n nn个物品每个物品救出需要t i t_iti时间、价值p i p_ipi且必须在d i d_idi时间之前救出严格小于d i d_idi。每次只能救一个物品求能带走的最大价值总和。这是一个带截止时间的01背包问题。算法选择按截止时间排序将物品按d i d_idi升序排序确保在考虑第i ii个物品时所有已处理的物品截止时间都不大于它01背包DPf [ j ] f[j]f[j]表示在时间j jj内能获得的最大价值逆序枚举为保证每个物品只选一次内层循环逆序枚举时间关键步骤读取输入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背包DPi 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].tf [ 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时间/空间复杂度时间复杂度O ( n × D ) O(n \times D)O(n×D)其中D max ( d i ) D \max(d_i)Dmax(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数组带截止时间的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背包【代码详解】#includebits/stdc.husingnamespacestd;// 常量与全局变量 constintN1005;// 最大物品数量intn;// 物品数量intf[20005];// 动态规划数组f[j] 表示在时间 j 内能获得的最大价值intans-1e9;// 最终答案初始化为极小值// 物品结构体structNode{intt;// 耗时intp;// 价值intd;// 截止时间}a[N];// 按截止时间升序排序 boolcmp(Node x,Node y){returnx.dy.d;}// 主函数 intmain(){// 读取物品数量cinn;// 读取每个物品的耗时、价值和截止时间for(inti1;in;i)cina[i].ta[i].pa[i].d;// 按截止时间升序排序sort(a1,an1,cmp);// 01 背包每个物品只能选一次for(inti1;in;i){// 逆序枚举时间保证每个物品只使用一次// 时间范围[a[i].t, a[i].d - 1]// 必须在截止时间之前完成所以最晚结束时间为 a[i].d - 1for(intja[i].d-1;ja[i].t;j--){f[j]max(f[j],f[j-a[i].t]a[i].p);}}// 在所有可能的时间点中取最大值// 最大截止时间为 a[n].d因此枚举到 a[n].d - 1for(inti1;ia[n].d-1;i)ansmax(ans,f[i]);// 输出结果coutansendl;return0;}【运行结果】3 2 4 7 2 5 6 3 6 7 11
题解：学而思编程 火灾
发布时间：2026/6/21 14:47:52
本文分享的必刷题目是从蓝桥云课、洛谷、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_itip i p_ipid i d_idi【输出】输出能带走的最大的价值总和【输入样例】3 2 4 7 2 5 6 3 6 7【输出样例】11【核心思想】问题分析给定n nn个物品每个物品救出需要t i t_iti时间、价值p i p_ipi且必须在d i d_idi时间之前救出严格小于d i d_idi。每次只能救一个物品求能带走的最大价值总和。这是一个带截止时间的01背包问题。算法选择按截止时间排序将物品按d i d_idi升序排序确保在考虑第i ii个物品时所有已处理的物品截止时间都不大于它01背包DPf [ j ] f[j]f[j]表示在时间j jj内能获得的最大价值逆序枚举为保证每个物品只选一次内层循环逆序枚举时间关键步骤读取输入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背包DPi 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].tf [ 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时间/空间复杂度时间复杂度O ( n × D ) O(n \times D)O(n×D)其中D max ( d i ) D \max(d_i)Dmax(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数组带截止时间的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背包【代码详解】#includebits/stdc.husingnamespacestd;// 常量与全局变量 constintN1005;// 最大物品数量intn;// 物品数量intf[20005];// 动态规划数组f[j] 表示在时间 j 内能获得的最大价值intans-1e9;// 最终答案初始化为极小值// 物品结构体structNode{intt;// 耗时intp;// 价值intd;// 截止时间}a[N];// 按截止时间升序排序 boolcmp(Node x,Node y){returnx.dy.d;}// 主函数 intmain(){// 读取物品数量cinn;// 读取每个物品的耗时、价值和截止时间for(inti1;in;i)cina[i].ta[i].pa[i].d;// 按截止时间升序排序sort(a1,an1,cmp);// 01 背包每个物品只能选一次for(inti1;in;i){// 逆序枚举时间保证每个物品只使用一次// 时间范围[a[i].t, a[i].d - 1]// 必须在截止时间之前完成所以最晚结束时间为 a[i].d - 1for(intja[i].d-1;ja[i].t;j--){f[j]max(f[j],f[j-a[i].t]a[i].p);}}// 在所有可能的时间点中取最大值// 最大截止时间为 a[n].d因此枚举到 a[n].d - 1for(inti1;ia[n].d-1;i)ansmax(ans,f[i]);// 输出结果coutansendl;return0;}【运行结果】3 2 4 7 2 5 6 3 6 7 11
