浅念づ昔夜's Blog

Like author, like book.

0%

CF372C Watching Fireworks is Fun

发表于 分类于
本文字数： 501 阅读时长 ≈ 2 分钟

Watching Fireworks is Fun - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

定义 Fi,jF_{i,j} 表示在位置 jj 观看烟花 ii 时，目前开心值的最大值。设 len=d(ti−ti−1)len=d(t_i-t_{i-1})，则

Fi,j=max⁡{Fi−1,k+bi−∣ai−j∣}F_{i,j}=\max\{F_{i-1,k}+b_i-|a_i-j|\}

其中 k∈[j−len,j+len]k\in [j-len,j+len]。

由于 FiF_i 由 Fi−1F_{i-1} 得来，因此可用滚动数组优化这一维。

如果这么做，时间复杂度是 O(n2m)O(n^2m) 的。我们考虑优化掉一个 nn，即 kk 的枚举过程。

假设 Fi,jF_{i,j} 是由 Fi−1,j′(j′<j)F_{i-1,j'}(j'<j) 转移得到的，那么在从 1∼n1\sim n 枚举 jj 的过程中将 Fi−1,jF_{i-1,j} 加入单调队列。保证队头的 FF 值最大，且 FF 值单调递减。这样 Fi,jF_{i,j} 就只用从队头的状态转移而来。当队头不再属于区间 [j−len,j+len][j-len,j+len] 时，则弹出队头。

同样的，考虑 (j′>j)(j'>j) 的转移，把单调队列清空，然后改为从 n∼1n\sim 1 枚举 jj，重复同样的操作即可。

时间复杂度 O(nm)O(nm)。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 150010;

ll n, m, d, ans, f[2][N], minn = 1e16;
deque<ll> que;
struct Node {
    ll a, b, t;
} a[N];

int main()
{
    scanf("%lld%lld%lld", &n, &m, &d);
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &a[i].a, &a[i].b, &a[i].t);
        ans += a[i].b;
    }
    for (int i = 1; i <= n; i++)
        f[1][i] = abs(a[1].a - i);
    for (int i = 2; i <= m; i++) {
        while (que.size()) que.pop_back();
        ll len = d * (a[i].t - a[i - 1].t);
        for (int j = 1; j <= n; j++)
            f[i & 1][j] = 1e16;
        for (int j = 1; j <= n; j++) {
            while (que.size() && que.front() + len < j)
                que.pop_front();
            while (que.size() && f[(i & 1) ^ 1][que.back()] >= f[(i & 1) ^ 1][j])
                que.pop_back();
            que.push_back(j);
            f[i & 1][j] = min(f[i & 1][j], f[(i & 1) ^ 1][que.front()] + abs(a[i].a - j));
        }
        while (que.size()) que.pop_back();
        for (int j = n; j; j--) {
            while (que.size() && que.front() - len > j)
                que.pop_front();
            while (que.size() && f[(i & 1) ^ 1][que.back()] >= f[(i & 1) ^ 1][j])
                que.pop_back();
            que.push_back(j);
            f[i & 1][j] = min(f[i & 1][j], f[(i & 1) ^ 1][que.front()] + abs(a[i].a - j));
        }
    }
    for (int i = 1; i <= n; i++)
        minn = min(minn, f[m & 1][i]);
    ans -= minn;
    printf("%lld", ans);
    return 0;
}