题解 | #最小花费#

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int L1, L2, L3, C1, C2, C3, A, B, N;
  while (cin >> L1 >> L2 >> L3 >> C1 >> C2 >> C3 >> A >> B >> N)
  {
    int d;
    vector<int> dis(N + 5, 0); // 距离数组，dis[i]表示从车站1到车站i的距离
    vector<int> dp(1e6, INT_MAX - 50000);// dp[i]表示从起点A到车站i的最小花费
    if (A > B) // 逆向正向一样的花费，所以这里保证A小于B即可
      swap(A, B);
    else if (A == B)
    {
      cout << 0 << endl;
      continue;
    }
    // 从起点即A到终点即A的花费，肯定是0
    dp[A] = 0;
    dis[1] = 0; //为了统一dis和dp的下标，dis往前凑了两格
    for (int i = 1; i < N; i++)
    {
      cin >> dis[i + 1];
    }
// 由递推公式可知要正向遍历
    for (int i = A; i <= B; i++)
    { // 要到车站B，肯定是从距离B小于L3的那些个车站做了一站到B的，于是遍历所以对于情况取最小值即可
      for (int j = i - 1; dis[i] - dis[j] <= L3 && j > 0; j--)
      {
        if (dis[i] - dis[j] <= L1) // 距离小于L1的花C1到B
        {
          dp[i] = min(dp[i], dp[j] + C1);
        }
        else if (dis[i] - dis[j] > L1 && dis[i] - dis[j] <= L2) // 同理花C2到B
        {
          dp[i] = min(dp[i], dp[j] + C2);
        }
        else // 同理花C3到B
        {
          dp[i] = min(dp[i], dp[j] + C3);
        }
      }
    }
    // 答案就为dp[B]
    cout << dp[B] << endl;
  }
  return 0;
}