题解：学而思编程 汽车变速

本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定初始速度v 1 v_1v1​、终点速度v 2 v_2v2​、总时间t tt和每秒最大速度变化量d dd。每秒内速度恒定，每秒之间速度变化不超过d dd。求路段的最大可能长度。这是一个线性动态规划问题，关键在于在速度变化约束下，最大化每秒行驶距离之和。

2. 算法选择：

   • 动态规划（DP）：f[i][j]表示第i ii秒速度为j jj时，前i ii秒走过的最大总路程
   • 状态转移：枚举前一秒的速度k kk，在速度变化允许范围内更新当前状态

3. 关键步骤：

   • 状态定义：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), j+d][max(0,j−d),j+d]）
     • f[i][j] = \max(f[i][j], f[i-1][k] + j)
   • 结果：f[t][v_2]（第t tt秒速度恰好为v 2 v_2v2​时的最大总路程）

4. 时间/空间复杂度：

   • 时间复杂度：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 dV=v1​+(t−1)⋅d为最大可能速度。具体为三重循环：时间t tt、速度V VV、速度变化范围2 d + 1 2d+12d+1
   • 空间复杂度：O ( t ⋅ V ) O(t \cdot V)O(t⋅V)，二维 DP 数组

5. 线性DP的核心思想：

   • 按时间线性递推：以时间为阶段，每一秒的状态只与前一秒有关
   • 速度作为第二维状态：将速度约束转化为状态维度，确保每秒速度变化不超过d dd
   • 最大化路径和：每秒贡献当前速度值j jj，通过 DP 累加求最大总路程
   • 边界条件处理：初始速度固定为v 1 v_1v1​，终止速度固定为v 2 v_2v2​
   • 适用于带约束的序列最优化问题

【算法标签】

#线性DP-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// ================= 常量与全局变量 =================constintN=105;// 最大时间步数constintM=1105;// 最大速度值intv1;// 初始速度intv2;// 最终速度intt;// 总时间intd;// 每秒钟速度的最大变化量intf[N][M];// 动态规划数组// f[i][j] 表示第 i 秒速度为 j 时，前 i 秒走过的最大总路程// ================= 主函数 =================intmain(){// 读取初始速度、最终速度、总时间和最大加速度cin>>v1>>v2>>t>>d;// 初始化 dp 数组为极小值memset(f,-0x3f,sizeof(f));// 边界条件：第 1 秒速度为 v1，路程为 v1f[1][v1]=v1;// 动态规划递推for(inti=2;i<=t;i++)// 枚举时间步{// 第 i 秒的可能速度范围：[0, v1 + (i-1)*d]for(intj=0;j<=v1+(i-1)*d;j++){// 第 i-1 秒的速度 k 必须在 [j-d, j+d] 范围内// 即速度变化不能超过 dfor(intk=max(0,j-d);k<=j+d;k++){// 转移：前 i-1 秒的路程 + 第 i 秒的路程 jf[i][j]=max(f[i][j],f[i-1][k]+j);}}}// 输出第 t 秒速度为 v2 时的最大总路程cout<<f[t][v2];return0;}

【运行结果】

5 6 4 2 26