题外话

前天英语考试，作文是

假如你是李华，你的美国朋友 Jack 对中国传统文化很感兴趣，他写信希望你能够告诉他有关春节的事情，请你写一封回信给他。开头和结尾已经给出，不计入总词数……

然后因为做过这道题，我就记住了 Firework 这个词，在这篇作文中竟然用上了（

solution

设 \(f_{i,j}\) 为第 \(i\) 个烟花 \(blooms\) 时，在第 \(j\) 个位置所能得到的最大开心值。

边界 \(f_{0,i}=0 \quad i \in [1,n]\)。

转移是显然的（好像这类题的朴素转移都挺显然的） \[ f_{i,j} = \min_{1 \le k \le n} { \{ f_{i-1,k} + b_i - \left| a_i-j \right| \} } \] 然后得到了一个喜人的复杂度 \(O(mn^2)\)

考虑优化，期望复杂度 \(O(mn)\)。

首先是 \(n \le 1.5 \times 10^5,m \le 300\)，空间不能承受，并且阶段 $ i$ 只与阶段 \(i-1\) 有关，滚动数组优化即可。

优化后只有两维，设当前维度为 $ w$，另一维为 \(w \text{ xor } 1\)。

不难发现转移的瓶颈在于枚举 \(k\)，且状态符合 1D/1D 模型，考虑单调队列优化。

设 $ i-1$ 阶段，位置在 \(k\)。对于 $ (i,j)$，能够向右移动到为区间为 \[ [k, \min \big( j+ d \cdot (t_i-t_{i-1}) \big) ] \] 枚举每个合法的 \(k\)，在单调队列中维护 \(f_{w \text{ xor } 1,j}\) 单调减。

能够向左到达的区间为 \[ [ \max \big( 1,j- d \cdot (t_i-t_{i-1}) \big), k ] \] 排除掉队首小于左边界的决策即可。

设队首为 $ k$。

最終の轉移！ \[ f_{w,j} = f_{w \text{ xor } 1,k}+b_i- \left| a_i-j \right| \] 虽然有枚举合法区间内的决策，但无伤大雅，可以看作常数。

复杂度 \(O(mn)\)。

#include<cstdio>
#include<iostream>
using namespace std;
#define R register
#define ll long long
const int N=150005, M=305;
int n, m, d, l, r, w=1, q[N];
ll a[M], b[M], t[M], f[2][N];
void sol() {
    R int i, j, k, o, u;
    for(int i=1;i<=n;++i) f[0][i]=0;
    for(int i=1;i<=m;++i) {
        l=k=1, r=0;
        for(int j=1;j<=n;++j) {
            o=min(1ll*n,j+d*(t[i]-t[i-1]));
            u=max(1ll,j-d*(t[i]-t[i-1]));
            for(;k<=o;++k) {
                while(l<=r&&f[w^1][q[r]]<=f[w^1][k]) --r;
                q[++r]=k;
            }
            while(l<=r&&q[l]<u) ++l;
            f[w][j]=f[w^1][q[l]]-abs(a[i]-j)+b[i];
        }
        w^=1;   
    }
}
signed main() {
    R int i;
    R ll ans=-(1ll<<60);
    scanf("%d%d%d",&n,&m,&d);
    for(i=1;i<=m;++i) scanf("%lld%lld%lld",&a[i],&b[i],&t[i]);
    sol();
    for(int i=1;i<=n;++i) ans=max(ans,f[w^1][i]);
    printf("%lld\n",ans);
}