本文分享的必刷题目是从蓝桥云课、洛谷、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-一维【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN10005,M505;// 定义最大物品数N和最大操作次数Mintn,m;// 物品数量n操作次数mintf[N][M];// 动态规划数组f[i][j]表示前i个物品使用j次操作的最大值inta[N];// 存储每个物品的值signedmain()// 主函数{cinnm;// 输入物品数量和操作次数for(inti1;in;i)// 读取所有物品的值cina[i];// 输入第i个物品的值memset(f,-0x3f,sizeof(f));// 初始化DP数组为负无穷f[0][0]0;// 初始状态0个物品0次操作值为0for(inti0;in;i)// 遍历每个物品{for(intj0;jm;j)// 遍历每种操作次数{if(f[i][j]0)continue;// 如果状态无效则跳过f[i1][j1]max(f[i1][j1],f[i][j]a[i1]);// 选择当前物品if(j0)// 如果操作次数为0f[i1][j]max(f[i1][j],f[i][j]);// 不选择当前物品else// 如果操作次数大于0{if(ijn)f[ij][0]max(f[ij][0],f[i][j]);// 跳过多个物品}}}coutf[n][0]endl;// 输出最终答案return0;// 程序正常结束}【运行结果】5 2 5 3 4 2 10 9