本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：4561. 挤奶时间 - AcWing题库
【题目描述】
在接下来的N NN个小时（编号为0 ∼ N − 1 0∼N−10∼N−1），农夫约翰可以进行挤奶。
约翰有一个时间区间列表，其中包含M MM个可能重叠的时间区间，在这些时间区间内，他可以挤奶。
每个区间包含一个起始时间，一个结束时间，以及在该时间区间内挤奶可以收获的牛奶量。
每个区间都是恰好在某个小时开始，恰好在某个小时结束。
当约翰选择在某个时间区间挤奶时，必须在整个时间区间内不停挤奶。
当约翰完成一次挤奶后，必须休息至少R RR小时，才能再次开始挤奶。
请你计算，约翰在N NN小时内，可以收获的最大牛奶量。
【输入】
第一行包含三个整数N , M , R N,M,RN,M,R。
接下来M MM行，每行包含三个整数a , b , c a,b,ca,b,c，表示一个区间的起始时间为a aa，结束时间为b bb，挤奶量为c cc。
【输出】
一个整数，表示最大挤奶量。
【输入样例】
12 4 2 1 2 8 10 12 19 3 6 24 7 10 31【输出样例】
43【算法标签】
#线性DP-一维
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=1000005,M=1005;intn,m,r;// n: 总时间，m: 挤奶时间段数量，r: 休息时间intf[M],ans;// f[i]: 以第i个时间段结尾的最大挤奶量，ans: 最大挤奶量structNode{intst,ed,val;// 开始时间，结束时间，产奶量}t[M];// 比较函数：按开始时间升序排序，开始时间相同则按结束时间升序boolcmp(Node x,Node y){if(x.st!=y.st)// 如果开始时间不同returnx.st<y.st;// 按开始时间升序排序returnx.ed<y.ed;// 开始时间相同则按结束时间升序}intmain(){scanf("%d%d%d",&n,&m,&r);// 输入总时间、挤奶时间段数量和休息时间for(inti=1;i<=m;i++)// 输入每个挤奶时间段的信息cin>>t[i].st>>t[i].ed>>t[i].val;sort(t+1,t+m+1,cmp);// 对挤奶时间段进行排序f[1]=t[1].val;// 初始化：以第一个时间段结尾的最大挤奶量ans=f[1];// 初始化答案for(inti=2;i<=m;i++)// 从第二个时间段开始动态规划{intmaxn=0;// 记录之前可衔接的最大挤奶量for(intj=1;j<i;j++)// 遍历之前的所有时间段{if(t[j].ed+r<=t[i].st)// 如果时间段j结束后有足够休息时间maxn=max(maxn,f[j]);// 更新最大挤奶量}f[i]=maxn+t[i].val;// 计算以时间段i结尾的最大挤奶量ans=max(ans,f[i]);// 更新全局最大值}cout<<ans<<endl;// 输出最大挤奶量return0;}【运行结果】
12 4 2 1 2 8 10 12 19 3 6 24 7 10 31 43
