洛谷-P9749 题解

发表于2023-11-05更新于2023-11-05

题目传送门

一道 dp 题……

好像大家写的都是贪心，这里给出一种 dp 的写法。

在 dp 之前，我们需要明确以下几个东西：

状态的表示，状态转移方程，边界条件跟答案的表示。

状态的表示

dpidp_i 表示到达第 ii 个站点所需要的最少钱数，wiw_i 表示在使用最少钱数到达第 ii 个站点时多余的路程。

状态转移方程

dpi=dpi−1+⌈vi−1−wi−1d⌉×pre_min(i−1)dp_i=dp_{i-1}+\lceil\frac{v_{i-1}-w_{i-1}}{d}\rceil\times pre\_min(i-1)

wi=⌈vi−1−wi−1d⌉−vi−1+wi−1w_i=\lceil\frac{v_{i-1}-w_{i-1}}{d}\rceil-v_{i-1}+w_{i-1}

其中 pre_min(i)pre\_min(i) 表示前 ii 个站点中最小的油价。

边界条件

dpi=0dp_i=0

wi=0w_i=0

答案的表示

dpndp_n

Code

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
#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;
}