CF372C Watching Fireworks is Fun

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

Solution

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

$F_{i,j}=\max\{F_{i-1,k}+b_i-|a_i-j|\}$

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

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

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

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

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

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

Code

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