乌龟兔子赛跑 完整解题思路梳理这道题是动态规划解决最短时间问题的经典竞赛题核心是模拟乌龟从起点到终点的所有可行行驶 / 充电策略通过动态规划记录每个点的最短用时最后和兔子的用时比较即可。我会从题目规则→核心思路→DP 定义→状态转移→代码落地一步步讲全程对照那版标准正确代码保证逻辑连贯、容易理解没有多余复杂概念。先明确「无歧义的题目核心规则」这是解题的前提规则理解错直接导致逻辑错也是之前容易踩坑的点赛道与点位赛道总长L起点是0终点是L中间有N个充电站乌龟只能在充电站 / 起点充电且充电后电动车满电续航 C最多电驱跑 C 的距离。行驶规则乌龟有两种行驶方式电驱速度 V1和脚蹬速度 V2且电驱优先级高于脚蹬—— 充电后先用电驱跑电用完跑满 C再脚蹬不能中途切换成纯脚蹬放弃电驱。充电规则起点默认满电不需要充电、不加充电时间只有在 ** 中间充电站非起点** 充电时才需要加固定充电时间T且充电后必满电。兔子规则兔子无限制全程匀速VR跑用时就是总长度L / 兔子速度VR。目标计算乌龟从起点到终点的最短用时和兔子用时比较输出谁赢。核心解题思路一句话概括把起点、所有充电站、终点按从起点到终点的顺序排成一个点位序列用动态规划记录「到达每个点位的最短用时」对于每个点位遍历所有能到达它的前序点位计算从「前序点位充电 / 行驶到当前点位」的用时取最小值作为当前点位的最短用时最终终点的最短用时就是乌龟的最优解。第一步定义 DP 状态动态规划的核心先把所有点位整理成数组p[]方便后续计算p[0] 0起点第 0 个点p[1] ~ p[N]N 个充电站输入后必须排序保证从起点到终点递增避免距离为负p[N1] L终点第 N1 个点总共有N2个点编号从0到N1。DP 状态定义dp[i]表示乌龟从起点出发到达第 i 个点p [i] 位置的最短用时。初始值dp[0] 0.0—— 起点用时为 0无争议目标值dp[N1]—— 到达终点的最短用时也是乌龟的最终用时。第二步状态转移怎么从前面的点推当前点的最短用时这是最关键的一步核心逻辑是要算到达 i 点的最短用时就看所有能走到 i 点的前序点 jj i计算从 j 到 i 的用时加上到达 j 点的最短用时 dp [j]取所有结果的最小值就是 dp [i]。针对每个 i 点遍历 j 点0 ≤ j i分 3 步计算「j→i 的总用时」步骤 1计算 j 到 i 的实际距离len p[i] - p[j]因为 p 数组已排序len 一定是正的。步骤 2计算 j 到 i 的行驶用时核心按题目规则算电驱 脚蹬的混合用时根据「电驱先跑满续航剩余脚蹬」的规则分两种情况若len ≤ C距离≤续航电驱能跑全程行驶用时 1.0 * len / V1若len C距离 续航先电驱后脚蹬行驶用时 1.0*C/V1 1.0*(len-C)/V2注乘 1.0 是为了把 int 转成浮点型避免整数除法取整导致精度错误。步骤 3判断是否需要加充电时间核心起点不充电只有从非起点的 j 点j ≥ 1即中间充电站出发时才需要在 j 点充电加充电时间T起点 j0 出发时默认满电不加T若j ! 0总用时 T若j 0无操作不加时间。状态转移公式综合以上 3 步从 j 到 i 的总耗时 到达 j 的最短用时dp[j] j→i 的行驶用时 j≠0 时的充电时间 T。对所有 j i 计算上述值取最小值赋值给dp[i]即dp[i] min{ dp[j] 行驶用时 (j≠0 ? T : 0) }j 从 0 到 i-1。第三步最终结果判断计算兔子的用时rabbit_time 1.0 * L / VR乌龟的用时turtle_time dp[N1]终点的最短用时比较两者若turtle_time rabbit_time乌龟赢输出What a pity rabbit!否则兔子赢输出Good job, rabbit!注OJ 对输出字符串要求极严大小写、标点、空格必须完全一致。第四步代码落地的关键细节OJ 提交必注意避免 WA/PE/RE以上是纯逻辑写成代码时需注意几个 OJ 高频坑也是标准代码里的关键细节充电站排序输入的充电站位置大概率是乱序的必须用sort排好序否则p[i]-p[j]会为负计算错误数组初始化dp 数组不需要提前初始化因为每个 dp [i] 都是通过遍历 j 取最小值得到的只需给dp[0]0.0即可数据类型dp 数组必须是浮点型double/float因为用时是小数int 会丢失精度输入输出竞赛中用scanf/printf比cin/cout更高效且避免格式问题若用 C需加ios::sync_with_stdio(false); cin.tie(0);加速循环边界点位编号从 0 到 N1所以外层循环 i 要遍历1 ~ N1内层循环 j 遍历0 ~ i-1多组测试用例题目要求多组输入直到输入结束scanf(%d,L)!EOF或cinL。整体解题流程流程图版更直观plaintext开始 → 输入赛道长度L → 输入N/C/T和VR/V1/V2 → 构建点位数组p[] → 排序p[] → 初始化dp[0]0.0 → 外层循环i遍历1~N1所有后续点 → 初始化当前最小值为极大值 → 内层循环j遍历0~i-1所有前序点 → 计算j→i的距离len → 计算j→i的行驶用时 → 计算j→i的总耗时dp[j]行驶用时充电时间 → 更新当前最小值 → dp[i] 当前最小值 → 计算兔子用时 → 比较乌龟dp[N1]和兔子用时 → 输出结果 → 继续下一组输入直到输入结束 → 结束核心关键点回顾记住这 3 点解题不跑偏DP 状态dp[i]是到达第 i 个点的最短用时点位必须排序状态转移遍历所有前序点 j计算 j→i 的「dp [j] 行驶用时 充电时间」取最小值行驶和充电规则是核心规则细节① 先电驱后脚蹬不放弃电驱② 起点满电不充电只有中间充电站加充电时间。#include stdio.h #include algorithm #include math.h using namespace std; const double INF 1e18; // 无穷大用于初始化 int main() { int L; // 多组输入直到EOF while (scanf(%d, L) ! EOF) { int N, C, T; int VR, VT1, VT2; scanf(%d %d %d, N, C, T); scanf(%d %d %d, VR, VT1, VT2); // 存储充电站位置下标1~N int pos[105] {0}; for (int i 1; i N; i) { scanf(%d, pos[i]); } // 排序充电站关键保证从起点到终点递增 sort(pos 1, pos N 1); // 构造完整点位序列起点(0)、充电站、终点(L) pos[0] 0; pos[N1] L; int total_point N 2; // DP数组初始化 double dp[105]; dp[0] 0.0; for (int i 1; i total_point; i) { dp[i] INF; } // 状态转移 for (int i 1; i total_point; i) { for (int j 0; j i; j) { int len pos[i] - pos[j]; // 计算行驶用时 double drive_time; if (len C) { drive_time 1.0 * len / VT1; } else { drive_time 1.0 * C / VT1 1.0 * (len - C) / VT2; } // 计算总用时j≠0时加充电时间 double total_time dp[j] drive_time; if (j ! 0) { total_time T; } // 更新最短用时 if (total_time dp[i]) { dp[i] total_time; } } } // 比较胜负 double rabbit_time 1.0 * L / VR; double turtle_time dp[N1]; if (turtle_time rabbit_time) { printf(What a pity rabbit!\n); } else { printf(Good job, rabbit!\n); } } return 0; }