本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程汽车变速【题目描述】小猴开着车通过某路段。路段的入口和出口设有测速装置它们测量出汽车在起点速度为v 1 v_1v1​​ 米/秒终点速度为v 2 v_2v2​​ 米/秒还知道小猴通过这段路用了t tt秒。假设每秒内的速度恒定在每秒之间小猴可以改变汽车速度但是由于汽车性能的限制新的速度与之前速度的差值不能超过d dd。求这个路段的最大可能长度单位为米。【输入】第一行包含两个整数v 1 v_1v1​​ 和v 2 v_2v2​​ 。第二行包含两个整数t tt和d dd。数据保证一定有解。【输出】仅有一个数表示以米为单位的路段最大可能长度。【输入样例】5 6 4 2【输出样例】26【核心思想】问题分析给定初始速度v 1 v_1v1​、终点速度v 2 v_2v2​、总时间t tt和每秒最大速度变化量d dd。每秒内速度恒定每秒之间速度变化不超过d dd。求路段的最大可能长度。这是一个线性动态规划问题关键在于在速度变化约束下最大化每秒行驶距离之和。算法选择动态规划DPf[i][j]表示第i ii秒速度为j jj时前i ii秒走过的最大总路程状态转移枚举前一秒的速度k kk在速度变化允许范围内更新当前状态关键步骤状态定义f[i][j]表示第i ii秒速度为j jj时前i ii秒的最大总路程初始化memset(f, -0x3f, sizeof(f))f[1][v_1] v_1$第一秒速度为v 1 v_1v1​路程为v 1 v_1v1​状态转移枚举时间i ii从2 22到t tt枚举第i ii秒的速度j jj范围[ 0 , v 1 ( i − 1 ) × d ] [0, v_1 (i-1) \times d][0,v1​(i−1)×d]枚举第i − 1 i-1i−1秒的速度k kk范围[ max ⁡ ( 0 , j − d ) , j d ] [\max(0, j-d), jd][max(0,j−d),jd]f[i][j] \max(f[i][j], f[i-1][k] j)结果f[t][v_2]第t tt秒速度恰好为v 2 v_2v2​时的最大总路程时间/空间复杂度时间复杂度O ( t ⋅ V ⋅ d ) O(t \cdot V \cdot d)O(t⋅V⋅d)其中V v 1 ( t − 1 ) ⋅ d V v_1 (t-1) \cdot dVv1​(t−1)⋅d为最大可能速度。具体为三重循环时间t tt、速度V VV、速度变化范围2 d 1 2d12d1空间复杂度O ( t ⋅ V ) O(t \cdot V)O(t⋅V)二维 DP 数组线性DP的核心思想按时间线性递推以时间为阶段每一秒的状态只与前一秒有关速度作为第二维状态将速度约束转化为状态维度确保每秒速度变化不超过d dd最大化路径和每秒贡献当前速度值j jj通过 DP 累加求最大总路程边界条件处理初始速度固定为v 1 v_1v1​终止速度固定为v 2 v_2v2​适用于带约束的序列最优化问题【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;// 常量与全局变量 constintN105;// 最大时间步数constintM1105;// 最大速度值intv1;// 初始速度intv2;// 最终速度intt;// 总时间intd;// 每秒钟速度的最大变化量intf[N][M];// 动态规划数组// f[i][j] 表示第 i 秒速度为 j 时前 i 秒走过的最大总路程// 主函数 intmain(){// 读取初始速度、最终速度、总时间和最大加速度cinv1v2td;// 初始化 dp 数组为极小值memset(f,-0x3f,sizeof(f));// 边界条件第 1 秒速度为 v1路程为 v1f[1][v1]v1;// 动态规划递推for(inti2;it;i)// 枚举时间步{// 第 i 秒的可能速度范围[0, v1 (i-1)*d]for(intj0;jv1(i-1)*d;j){// 第 i-1 秒的速度 k 必须在 [j-d, jd] 范围内// 即速度变化不能超过 dfor(intkmax(0,j-d);kjd;k){// 转移前 i-1 秒的路程 第 i 秒的路程 jf[i][j]max(f[i][j],f[i-1][k]j);}}}// 输出第 t 秒速度为 v2 时的最大总路程coutf[t][v2];return0;}【运行结果】5 6 4 2 26