Watching Mooloo

题意

Bessie 有 $N$ 天要看 Mooloo，观看日为：

text

1d_1 < d_2 < ... < d_N

订阅连续 $x$ 天需要花费：

x + K

可以在任意一天开始订阅，也可以多次订阅。

求覆盖所有观看日的最小花费。

思路

先看一个小数据 DP：

cpp

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:48
 * update_at: 2026-07-11 16:49
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const long long INF = (1LL << 60);

int n;
long long k;
long long day_arr[MAXN];
long long dp[MAXN]; // dp[i] 表示覆盖前 i 个观看日的最小费用

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> day_arr[i];
    }

    for (int i = 1; i <= n; i++) {
        dp[i] = INF;
    }
    dp[0] = 0;

    // 小数据暴力 DP：枚举最后一个订阅段覆盖哪些观看日。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            long long len = day_arr[i] - day_arr[j] + 1;
            dp[i] = min(dp[i], dp[j - 1] + len + k);
        }
    }

    cout << dp[n] << '\n';

    return 0;
}

这个 DP 枚举最后一个订阅段覆盖哪些观看日。如果最后一段从第 j 个观看日覆盖到第 i 个观看日，那么这段长度是：

text

1d[i] - d[j] + 1

费用是：

text

1d[i] - d[j] + 1 + K

满分做法可以更简单。考虑相邻两个观看日 d[i-1] 和 d[i]。

在已经覆盖到 d[i-1] 后，对于 d[i] 只有两种选择：

继续当前订阅，从 d[i-1] 延长到 d[i]，新增费用是：

text

1d[i] - d[i-1]

在 d[i] 重新买一个一天订阅，新增费用是：

text

1K + 1

两者取较小即可。

第一天必须新开订阅，费用为 K+1。之后逐个相邻观看日累加：

text

1min(d[i] - d[i-1], K + 1)

为什么这样是对的？因为两个相邻观看日之间是否断开，只影响这两个观看日之间的空白天数和是否多付一次固定费用 K。每个间隔可以独立决定：间隔短就继续订阅，间隔长就断开重开。

代码

cpp

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
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:48
 * update_at: 2026-07-11 16:49
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long k;
long long day_arr[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> day_arr[i];
    }

    long long ans = k + 1;
    for (int i = 2; i <= n; i++) {
        long long keep_cost = day_arr[i] - day_arr[i - 1];
        long long restart_cost = k + 1;
        ans += min(keep_cost, restart_cost);
    }

    cout << ans << '\n';

    return 0;
}

复杂度

只扫描观看日一次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题可以看成把观看日分成若干连续订阅段。

相邻观看日之间的断点只需要比较“续订的额外天数”和“重新订阅的固定费用”，取较小值即可。

目录

题意

思路

代码

复杂度

总结