本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P1353 [USACO08JAN] Running S - 洛谷 (luogu.com.cn)
【题目描述】
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行n nn分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。
贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i ii分钟内跑步，她可以在这一分钟内跑d i d_idi米，并且她的疲劳度会增加1 11。不过，无论何时贝茜的疲劳度都不能超过m mm。
如果贝茜选择休息，那么她的疲劳度就会每分钟减少1 11，但她必须休息到疲劳度恢复到0 00为止。在疲劳度为0 00时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0 00。
还有，在n nn分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0 00，否则她将没有足够的精力来对付这一整天中剩下的事情。
请你计算一下，贝茜最多能跑多少米。
【输入】
第一行两个正整数n , m n,mn,m。
接下来n nn行，每行一个正整数d i d_idi。
【输出】
输出一个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离。
【输入样例】
5 2 5 3 4 2 10【输出样例】
9【算法标签】
#普及plus #线性DP-一维
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=10005,M=505;// 定义最大物品数N和最大操作次数Mintn,m;// 物品数量n，操作次数mintf[N][M];// 动态规划数组，f[i][j]表示前i个物品使用j次操作的最大值inta[N];// 存储每个物品的值signedmain()// 主函数{cin>>n>>m;// 输入物品数量和操作次数for(inti=1;i<=n;i++)// 读取所有物品的值cin>>a[i];// 输入第i个物品的值memset(f,-0x3f,sizeof(f));// 初始化DP数组为负无穷f[0][0]=0;// 初始状态：0个物品，0次操作，值为0for(inti=0;i<n;i++)// 遍历每个物品{for(intj=0;j<=m;j++)// 遍历每种操作次数{if(f[i][j]<0)continue;// 如果状态无效则跳过f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+a[i+1]);// 选择当前物品if(j==0)// 如果操作次数为0f[i+1][j]=max(f[i+1][j],f[i][j]);// 不选择当前物品else// 如果操作次数大于0{if(i+j<=n)f[i+j][0]=max(f[i+j][0],f[i][j]);// 跳过多个物品}}}cout<<f[n][0]<<endl;// 输出最终答案return0;// 程序正常结束}【运行结果】
5 2 5 3 4 2 10 9
