题意

有 $n$ 个相邻 距离为 $1$ 的地点编号为 $1-n$. 有 $m$ 个事件分别在地点 $a_i$ 时间 $t_i$ 发生, 在 $t_i$ 时位于地点 $x_{t_i}$ 能获得 $b_i-|a_i-x_{t_i}|$ 的收益, 要求 $|x_i-x_{i+1}|\le d$. 求 $\max{(\sum{b_i-|a_i-x_{t_i}|})}$.

其中 $1\le n\le 150000, 1\le m\le 300, 1\le d\le n$;

$1\le a_i\le n, 1\le b_i\le 10^9, 1\le t_i\le 10^9$.

思路

考虑 DP. 先令 $f[x][y]$ 为 $x_{t_x}=y$ 情况下的 $\max{(\sum_{i=1}^{x}{b_i-|a_i-x_{t_i}|})}$. 再用瞪眼法, 得出递推式子: $$ f[i][j]=\max{(f[i-1][k]+b_i-|a_i-j|)} \\ :k\in[x_{t_{i-1}}-d\times(t_i-t_{i-1})),x_{t_{i-1}}+d\times(t_i-t_{i-1}))]\cap [1,n] $$

时间复杂度是 $\Omicron(n^2m)$. 考虑如何优化, 把 $b_i-|a_i-j|$ 提出. $$ f[i][j]=\max{(f[i-1][k])}+b_i-|a_i-j| $$ 发现可以用单调栈均摊, 复杂度 $\Omicron(nm)$.

再考虑内存, 可以看出 $f[i][j]$ 的递推式只需要 $f[i-1][j]$, 把第一维优化掉.

代码

#define ll long long
const int N = 1.5e5+5, M = 305;
ll a[M], b[M], t[M];
ll f[2][N]={0};
int main(){
    int n, m, d;
    cin>>n>>m>>d;
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>t[i];
    for(int i=1;i<=m;i++){
        deque<int> q;
        ll h = (t[i]-t[i-1])*d;
        for(int j=1, k=1;j<=n;j++){
            while(k<=j+h&&k<=n){
                while(!q.empty()&&f[i&1][q.back()]<=f[i&1][k]) q.pop_back();
                q.push_back(k), k++;
            }
            while(!q.empty()&&q.front()<(j-h)) q.pop_front();
            f[!(i&1)][j]=f[i&1][q.front()]+b[i]-abs(a[i]-j);
        }
    }
    ll ans=-INT_MAX;
    for(int i=1;i<=n;i++) ans=max(ans, f[!(m&1)][i]);
    cout<<ans<<endl;
    return 0;
}