最优乘车

最优乘车问题是一个经典的动态规划问题，它的目标是在满足一定条件下，选择一组车次和转车方案，使总的时间最短。

具体来说，最优乘车问题可以描述为：在一条线路上，有 n 辆车，第 i 辆车从起点出发的时间为 ti，到达终点的时间为 si，车上的乘客必须在起点等车，并在终点下车。每辆车的乘车时间为 ci，任何两辆车之间都可以转车，但是要满足乘客等待时间不超过一个给定的阈值 w。现在需要确定一个乘车计划，使得从起点到终点的总时间最短。

最优乘车问题可以使用动态规划算法求解。具体来说，可以定义一个状态 dp(i) 表示从起点到第 i 辆车的最短时间。如果第 i 辆车的出发时间为 ti，那么有：

dp(i) = min(dp(j) + max(0, ti - sj - ci - w))

其中，j 是满足 sj ≤ ti 的最大的车次，因为所有在 j 之前到达终点的车都可以作为第 i 辆车的转车方案。而 max(0, ti - sj - ci - w) 表示从第 j 辆车到第 i 辆车的等待时间，如果这个时间为负数，说明第 i 辆车可以直接在 j 辆车的终点上车。

最终的答案是 dp(n)。

下面是使用 C++ 实现最优乘车问题的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    vector<int> t(n+1), s(n+1), c(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> s[i] >> c[i];
    }
    vector<int> dp(n+1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int j = i - 1;
        while (j >= 0 && s[j] + c[j] + w > t[i]) {
            j--;
        }
        dp[i] = dp[j+1] + max(0, t[i] - s[j+1] - c[j+1] - w);
        for (int k = j+2; k < i; k++) {
            dp[i] = min(dp[i], dp[k] + max(0, t[i] - s[k] - c[k] - w));
        }
    }
    cout << dp[n] << endl;
    return 0;
}

该代码中，首先读入 n 和 w，然后读入每一辆车的 ti、si、ci，然后使用 dp 数组计算从起点到每一辆车的最短时间，最终输出 dp[n]。