题目链接

题目描述

一个城镇有 $n$ 个区域，从左到右编号为 $1$ 到 $n$，每个区域之间距离 $1$ 个单位距离。

节日中有 $m$ 个烟火要放，给定放的地点 $a_i$ 时间 $t_i$，如果你当时在区域$x$，那么你可以获得 $b_i - \vert a_i - x\vert$ 的开心值。

你每个单位时间可以移动不超过 $d$ 个单位距离。

你的初始位置是任意的（初始时刻为 $1$ ），求你通过移动能获取到的最大的开心值。

$1 \le n \le 150000$

$1 \le m \le 300$

简要做法

可以想出 $f(i,j)$ 表示 第 $i$ 个烟花的时候在 第 $j$ 个区域的时候的开心度最大值

$f(i, j) = max(\ f(i, j), \ f(i - 1, k) + b_i - \vert a_i - x\vert \ )$

$len = ({t_i} - {t_{i-1}}) * d$

$k \in [j - len, j + len]$

空间好像炸了，把 $i$ 滚掉就行了

时间好像炸了，尝试优化

$ans = max_{i=1}^{m}( \ {f(m,i)} \ )$

直接把 $\sum_{i=1}^{m}{b_i}$ 扔进 ans 里

$ans = \sum_{i=1}^{m}{b_i} - min_{i=1}^{m}( \ {f(m,i)} \ )$

单调队列即可

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>

typedef long long ll;

const ll N = 15e4 + 5;
const ll M = 3e2 + 5;
const ll INF = 1LL << 60;

ll n, m, d, ans = INF, sum;
ll a[N], b[N], t[N];
ll f[2][N];
ll Q[N];

ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

signed main()
{
    n = read(), m = read(), d = read();
    for (ll i = 1; i <= m; i++)
        a[i] = read(), b[i] = read(), t[i] = read();
    for (ll i = 1, k = 0; i <= m; i++, k ^= 1)
    {
        sum += b[i];
        ll len = (t[i] - t[i - 1]) * d, head = 1, tail = 0;
        for (ll j = 1; j <= n; j++)
        {
            while (head <= tail and Q[head] < j - len)
                ++head;
            while (head <= tail and f[k][Q[tail]] > f[k][j])
                --tail;
            Q[++tail] = j;
            f[k ^ 1][j] = f[k][Q[head]] + abs(a[i] - j);
        }
        head = 1, tail = 0;
        for (ll j = n; j >= 1; j--)
        {
            while (head <= tail and Q[head] > j + len)
                ++head;
            while (head <= tail and f[k][Q[tail]] > f[k][j])
                --tail;
            Q[++tail] = j;
            f[k ^ 1][j] = std::min(f[k ^ 1][j], f[k][Q[head]] + abs(a[i] - j));
        }
    }
    for (ll i = 1; i <= n; i++)
        ans = std::min(ans, f[m % 2][i]);
    printf("%lld", sum - ans);
    return 0;
}