复赛三：摆渡车(bus)
洛谷：P5017
OJ：P4961
代码功能概述：
这个代码旨在解决一个关于摆渡车调度的问题，目的是将多个学生送往人民大学，并使得所有同学的等车时间之和最小。通过使用动态规划（dp）的方法来计算最优调度策略。
代码的思路是通过动态规划，将相邻同学的时间差（gap）进行分组和处理，找出每个子问题中的最优解，从而求出全局的最优解。
变量定义与说明：
dp[505][105][505]：三维动态规划数组，dp[i][j][k]表示的是 从第i位同学开始计算，在摆渡车还有j分钟回来、已经有k个同学等待上车的情况下，从第i位同学及其后续同学的最小等待时间之和。ti[505]：存储每个同学到达车站的时间。gap[505]：存储相邻两个同学到达车站的时间差，即gap[i] = ti[i+1] - ti[i]。n和m：n表示同学数量，m表示摆渡车往返一趟所需的时间。
计算时间差：
for(int i=1; i<n; ++i) gap[i] = ti[i+1] - ti[i];
这里计算相邻两位同学的到达时间差，存储在 gap 数组中。这将用于后续动态规划中，决定在当前时间间隔下如何安排摆渡车发车。
动态规划数组的初始化：
for(int k=1; k<=n; ++k){
for(int j=1; j<=m; ++j)
dp[n][j][k] = j*k;
}
这段代码的目的是为最后一个同学的状态进行初始化，因为第 n 位同学之后已经没有其他同学了，所以此时的等待时间仅取决于当前的 j 和 k，即剩余等待时间 j 和当前等待上车的同学人数 k。
动态规划的状态转移：
for(int i=n-1; i>=1; --i){
for(int k=1; k<=i; ++k){
for(int j=0; j<=min(gap[i],m); ++j){
dp[i][j][k] = min(dp[i+1][0][k+1]+gap[i]*k, dp[i+1][max(0,m-gap[i]+j)][1] + j*k);
}
for(int j=min(gap[i]+1,m+1); j<=m; ++j){
dp[i][j][k] = dp[i+1][j-gap[i]][k+1] + gap[i]*k;
}
}
}
这个代码片段是动态规划算法的核心，用于解决摆渡车调度问题。它的目的是通过状态转移来计算从第 i 位同学开始时最优的等待时间方案，考虑摆渡车的往返时间 m 和同学到达车站的时间差 gap[i]。代码包含两个核心部分：状态转移和计算最优解。下面我们逐步进行详细分析。
代码逻辑逐步解析：
1. 外层循环 for (int i = n - 1; i >= 1; --i)：
- 这个循环从第
n-1位同学开始，向前遍历到第1位同学。 i表示当前正在处理的同学，i从n-1到1，表示从后往前逐步处理。这样可以保证每个状态dp[i]的计算是基于后续同学的最优解dp[i+1]。
2. 第二层循环 for (int k = 1; k <= i; ++k)：
k表示当前摆渡车上已经有k位同学等待上车。也就是说，当我们处理第i位同学时，已经有k位同学准备上车。- 这个循环决定了在每个状态下，摆渡车上的等待人数。
3. 第三层循环 for (int j = 0; j <= min(gap[i], m); ++j)：
j表示摆渡车还有多少时间才能返回，j是等待时间的剩余时间。min(gap[i], m)：因为摆渡车的往返时间是固定的m，但如果两个同学之间的时间差gap[i]小于m，则我们只需要等待gap[i]分钟。
状态转移方程：
dp[i][j][k] = min(dp[i+1][0][k+1] + gap[i] * k, dp[i+1][max(0, m - gap[i] + j)][1] + j * k);这是核心的状态转移方程，表示第 i 位同学及后续同学的最优等待时间。它有两种状态转移方式：
- 状态1：将第
i位同学与后面的同学一起上车： dp[i+1][0][k+1] + gap[i] * k：dp[i+1][0][k+1]表示从第i+1位同学开始，摆渡车立即发车，k+1表示包括当前同学在内的所有人一起上车。gap[i] * k表示第i位同学与之前k位同学等待的时间（gap[i]是他们的时间差）。
- 状态2：第
i位同学单独发车： dp[i+1][max(0, m - gap[i] + j)][1] + j * k：dp[i+1][max(0, m - gap[i] + j)][1]表示在第i+1位同学处，摆渡车要在max(0, m - gap[i] + j)分钟后回来，也就是考虑m分钟的往返时间和gap[i]的时间差。j * k表示当前这趟车上k位同学的等待时间。
4. 第二个内层循环 for (int j = min(gap[i] + 1, m + 1); j <= m; ++j)：
- 这个循环处理
j大于gap[i]的情况，也就是说，摆渡车的往返时间更长，需要考虑更多的等待时间。
dp[i][j][k] = dp[i+1][j-gap[i]][k+1] + gap[i] * k;dp[i+1][j - gap[i]][k+1]表示在摆渡车回来后，从第i+1位同学开始，车上已经有k+1位同学，剩余等待时间为j - gap[i]。gap[i] * k仍然表示这k位同学等待的时间。
总结：
- 这段代码的核心思想是通过动态规划来计算第
i位同学及其后续同学的最小等待时间。 - 状态转移方程中考虑了两种情况：一是将当前同学与后面的同学一起上车，二是当前同学单独发车。
- 通过遍历时间
j和等待人数k，该算法逐步计算出所有同学的最优等待时间分配方案。
这段代码通过遍历同学、时间差以及等待人数，逐步将问题分解成多个子问题，利用动态规划有效地解决了如何安排摆渡车发车以最小化所有同学等待时间的问题。
代码总结：
该代码利用了动态规划来最小化所有同学的等待时间。核心思路是通过 dp[i][j][k] 表示状态，逐步递推更新不同分组下的最优解。在计算时，考虑到学生到达的时间差 gap[i] 以及摆渡车的往返时间 m，通过两种状态转移方式来优化每次发车的时机。
- 关键点：通过动态规划的转移方程，我们可以有效减少复杂度，避免暴力搜索所有可能的调度方案，从而找到最优解。
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <iostream> #include <algorithm> using namespace std; // 定义三维动态规划数组 dp，存储不同情况下的最优解 int dp[505][105][505]; int ti[505]; // 存储每个同学的到达时间 int gap[505]; // 存储相邻同学到达时间的差值 int main(){ int n,m; // 输入 n（同学数量）和 m（摆渡车往返所需时间） cin >> n >> m; // 输入每位同学到达车站的时间 for(int i=1; i<=n; ++i) cin >> ti[i]; // 对同学的到达时间进行排序 sort(ti + 1, ti + 1 + n); // 计算相邻同学到达时间的差值，存储到 gap 数组中 for(int i=1; i<n; ++i) gap[i] = ti[i+1] - ti[i]; // 初始化动态规划数组，处理最后一位同学的情况 // dp[n][j][k] 表示第 n 位同学时，时间间隔 j，当前是第 k 组的最优等待时间 for(int k=1; k<=n; ++k) { for(int j=1; j<=m; ++j) { // 初始化为 j * k，表示最后一位同学的等待时间与分组数的乘积 dp[n][j][k] = j * k; } } // 从倒数第二个同学开始，进行动态规划状态转移 for(int i = n-1; i >= 1; --i) { // 枚举当前考虑的分组数 k for(int k = 1; k <= i; ++k) { // 枚举摆渡车的时间间隔 j，处理 gap[i] <= m 的情况 for(int j = 0; j <= min(gap[i], m); ++j) { // 状态转移：dp[i][j][k] 由第 i+1 位同学的状态转移而来 dp[i][j][k] = min( // 情况1：当前同学和后面的同学分为一组 dp[i+1][0][k+1] + gap[i] * k, // 情况2：当前同学单独一组 dp[i+1][max(0, m - gap[i] + j)][1] + j * k ); } // 处理 gap[i] > m 的情况 for(int j = min(gap[i] + 1, m + 1); j <= m; ++j) { // 状态转移：dp[i][j][k] 更新为最优解 dp[i][j][k] = dp[i+1][j-gap[i]][k+1] + gap[i] * k; } } } // 输出结果，即最小等待时间的和 cout << dp[1][0][1]; return 0; } |