(cf372c) Watching Fireworks is Fun

发表于 分类于 ，

原题链接

思路:

单调队列优化 dp 模板

设 \(d_{i,j}\) 为当放第 \(i\) 个烟花时在位置 \(j\) 的最大快乐值，则有转移方程:

\[ d_{i,j} = \max_{k}\{d_{i-1,k}\} + b_i - |a_i-j| \\ k \in [j-\Delta td, j+\Delta td] \cap [1,n] \]

max 所取区间左右端点随 j 增加单调不降， 所以可以使用单调队列在 \(O(1)\) 的时间上取最大值.

代码:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cctype>
#include <climits>
#include <deque>
using namespace std;
using LL = long long;
const int Mn(150500), Mm(350);
template<typename T> void qrd(T& x) {   //快读
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x, Ts&... xs) {
    qrd(x); qrd(xs...);
}

inline LL labs(LL x) {
    return x<0 ? -x : x;
}

struct Qd {     //队列内元素
    LL x, p;
    bool operator < (const Qd& rhs) const {
        return x<rhs.x;
    }
};
struct Grq {    //单调队列封装
    deque<Qd> q;
    Qd front() {
        return q.front();
    }
    void pop() {
        q.pop_front();
    }
    void push(Qd x) {
        while(!q.empty() && q.back()<x) {
            q.pop_back();
        }
        q.push_back(x);
    }
    void clear() {
        q.clear();
    }
} gq;

int a[Mm];
LL b[Mm], t[Mm];
LL f[2][Mn];    //dp数组, 滚动数组

int main() {
    int n,m;
    LL d;
    qrd(n,m,d);
    for(int i(1);i<=m;++i) {
        qrd(a[i],b[i],t[i]);
    }
    t[0] = 1;
    for(int i(1);i<=m;++i) {
        gq.clear();
        for(int j(1);j<=n && j<=(t[i]-t[i-1])*d;++j) {  //初始化
            gq.push({f[(i&1)^1][j],j});
        }
        for(int j(1);j<=n;++j) {
            if(j+(t[i]-t[i-1])*d<=n) {  //入队
                gq.push({f[(i&1)^1][j+(t[i]-t[i-1])*d],j+(t[i]-t[i-1])*d});
            }
            if(gq.front().p<j-(t[i]-t[i-1])*d) {    //若队首元素不在可取区间则出队
                gq.pop();
            }
            f[i&1][j] = gq.front().x + b[i] - labs(a[i]-j); //可取区间最大值即为gq.front()
        }
    }
    LL ans(LONG_LONG_MIN);
    for(int i(1);i<=n;++i) {
        ans = f[m&1][i] > ans ? f[m&1][i] : ans;
    }
    printf("%lld\n",ans);
    return 0;
}