[CF372C] Watching Fireworks is Fun - 单调队列优化dp

[CF372C] Watching Fireworks is Fun - 单调队列优化dp

Description

一个城镇有\(n\)个区域,从左到右\(1\)编号为\(n\),每个区域之间距离\(1\)个单位距离。 节日中有\(m\)个烟火要放，给定放的地点\(a_i\),时间\(t_i\),如果你当时在区域\(x\),那么你可以获得\(b_i - \vert a_i - x\vert\)的开心值。 你每个单位时间可以移动不超过\(d\)个单位距离。你的初始位置是任意的(初始时刻为\(1\)),求你通过移动能获取到的最大的开心值。\(n \le 150000, m \le 300\)

Solution

设 \(f[i][j]\) 表示放第 \(i\) 个烟花的时候站在第 \(j\) 个区域，目前收获的最大开心值

转移来源是定长区间，单调队列优化

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 150005;
const int M = 305;

struct Firework
{
    int a, b, t;
};

int n, m, d, f[2][N];
Firework obj[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m >> d;
    for (int i = 1; i <= m; i++)
    {
        cin >> obj[i].a >> obj[i].b >> obj[i].t;
    }

    for (int i = 1; i <= m; i++)
    {
        deque<pair<int, int>> que;
        int k = d * (obj[i].t - obj[i - 1].t);
        if (i == 1)
            k = 0;
        k = min(k, n);
        for (int j = 1; j <= k; j++)
        {
            while (que.size() && que.back().first < f[(i - 1) & 1][j])
                que.pop_back();
            que.push_back({f[(i - 1) & 1][j], j + k});
        }
        for (int j = 1; j <= n; j++)
        {
            if (j + k <= n)
            {
                while (que.size() && que.back().first < f[(i - 1) & 1][j + k])
                    que.pop_back();
                que.push_back({f[(i - 1) & 1][j + k], j + k + k});
            }
            while (que.size() && que.front().second < j)
                que.pop_front();
            if (que.size())
            {
                f[i & 1][j] = que.front().first + obj[i].b - abs(obj[i].a - j);
            }
        }
    }

    cout << *max_element(f[m & 1] + 1, f[m & 1] + n + 1) << endl;
}

[CF372C] Watching Fireworks is Fun - 单调队列优化dp

原文：https://www.cnblogs.com/mollnn/p/14638783.html