一道 dp 题。
好像大家写的都是贪心，这里给出一种 dp 的写法。
在 dp 之前，我们需要明确以下几个东西：
状态的表示，状态转移方程，边界条件跟答案的表示。
状态的表示
\(dp_i\) 表示到达第 \(i\) 个站点所需要的最少钱数，\(w_i\) 表示在使用最少钱数到达第 \(i\) 个站点时多余的路程。
状态转移方程
\[dp_i=dp_{i-1}+\lceil\frac{v_{i-1}-w_{i-1}}{d}\rceil\times pre\_min(i-1)
\]
\[w_i=\lceil\frac{v_{i-1}-w_{i-1}}{d}\rceil-v_{i-1}+w_{i-1}
\]
其中 \(pre\_min(i)\) 表示前 \(i\) 个站点中最小的油价。
边界条件
\[dp_i=0
\]
\[w_i=0
\]
答案的表示
\[dp_n
\]
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n, d, ans;
ll v[100005], a[100005], dp[100005], pm[100005], w[100005];
int main() {
// freopen("road.in", "r", stdin);
// freopen("road.out", "w", stdout);
ios :: sync_with_stdio(0);
cin >> n >> d;
pm[0] = 1e18;
for (int i = 1; i < n; i++) cin >> v[i];
for (int i = 1; i <= n; i++) {
cin >> a[i];
pm[i] = min(pm[i - 1], a[i]);
}
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + ceil(1.0 * (v[i - 1] - w[i - 1]) / d) * pm[i - 1];
w[i] = ceil(1.0 * (v[i - 1] - w[i - 1]) / d) * d - (v[i - 1] - w[i - 1]);
}
cout << dp[n];
return 0;
}