AcWing 3394. 最小花费
原题链接
简单
作者:
ᔠዂϤ
,
2022-01-12 17:54:55
,
所有人可见
,
阅读 510
动态规划
C++ 代码
#include <iostream>
using namespace std;
const int N = 1005, inf = 0x3f3f3f3f;
int d[N], dp[N]; // d[j]:记录站点 j 到站点 1 的距离
int l[3], c[3], x[3];
int a, b, n;
#define loop for (int j = 0; j != 3; j++)
int main()
{
loop cin >> l[j];
loop cin >> c[j];
cin >> a >> b >> n;
for (int i = 2; i <= n; i++)
cin >> d[i];
loop x[j] = a;
// x[j]:记录从 i 站点出发,用一张 j 类型的票能够反向到达的,编号最小的站
for (int i = a + 1; i <= b; i++)
{
loop while (d[i] - d[x[j]] > l[j]) x[j]++;
dp[i] = inf;
loop dp[i] = min(dp[i], dp[x[j]] + c[j]);
}
cout << dp[b];
}