P9123 [USACO23FEB] Watching Mooloo B 题解

liyuanchen2021 · 2023-03-07 18:39:21 · 题解

本题用到的算法是线性 DP。

对于第 d_1 天，只有一种选择——买票，当天花费为 k+1。

对于第 d_i 天，有两种选择：

• 买票，当天花费为 k+1；
• 不买票，当天花费为 d_i - d_{i-1}。

我们设 f_i 为前 d_i 天的花费总和，递推式如下：

• 若 i=1，则 f_i=k+1；
• 若 i>1，则 f_i=\min\{f_{i-1}+(k+1),f_{i-1}+(d_i-d_{i-1})\}。

最后输出 f_n 即可。

#include <iostream>
using namespace std;
long long d[100005], f[100005];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)    cin >> d[i];
    f[1] = k + 1ll;
    for (int i = 2; i <= n; i++)
        f[i] = min(f[i - 1] + (d[i] - d[i - 1]), f[i - 1] + (k + 1ll));
    cout << f[n] << endl;
    return 0;
}