题意
前言
学习一个新的算法，总是要仔细考虑一些深入的问题
题解
首先清楚单调队列是一个主要用来优化 dp 的算法，所以先想出 dp 转移式子，再通过单调队列优化掉一维的复杂度才是正常的打开方式
回归本题，很容易想到设计\(dp(i,j)\)表示前\(i\)个烟花的时候在第\(j\)个位置能获得的最大幸福值
转移也比较显然，再枚举一维\(k\)表示第\(i-1\)个烟火的时候在什么位置，就有\(dp(i,j)=max \{dp(i-1,k)\} +b_i-abs(a_i-j);\)
因为是一个区间单调地向右移动同时维护最大值，所以\(k\)这一维就可以单调队列优化了
需要注意的是，\(j\)的循环需要顺序和倒序分别枚举一次，因为要考虑到从\(j\)的左边和右边走到\(j\)的两种情况
由于有负值，dp 数组需要稍微特殊处理一下
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 1.5e5+10,M = 305;
inline ll read()
{
ll ret=0;char ch=‘ ‘,c=getchar();
while(!(c>=‘0‘&&c<=‘9‘)) ch=c,c=getchar();
while(c>=‘0‘&&c<=‘9‘) ret=(ret<<1)+(ret<<3)+c-‘0‘,c=getchar();
return ch==‘-‘?-ret:ret;
}
struct node
{
int a,b,t;
inline bool operator < (const node& oth) const {return t<oth.t;}
}f[M];
int dp[M][N];
int n,m,d,q[N];
int main()
{
n=read(),m=read(),d=read();
for(int i=1;i<=m;i++) f[i].a=read(),f[i].b=read(),f[i].t=read();
//sort(f+1,f+m+1); 输入保证t不下降
//memset(dp,-0x3f,sizeof(dp));
//for(int i=1;i<=n;i++) dp[m][i]=-INF;
for(int i=1;i<=m;i++)
{
int l=1,r=0;
for(int j=1;j<=n;j++)
{
while(r>=l&&j-q[l]>(f[i].t-f[i-1].t)*d) l++;
while(r>=l&&dp[i-1][q[r]]<=dp[i-1][j]) r--;
q[++r]=j;
if(r>=l) dp[i][j]=dp[i-1][q[l]]+f[i].b-abs(f[i].a-j);
//printf("dp:%d update\n",dp[i-1][q[l]]+f[i].b-abs(f[i].a-j));
}
l=1,r=0;
for(int j=n;j>=1;j--)
{
while(r>=l&&q[l]-j>(f[i].t-f[i-1].t)*d) l++;
while(r>=l&&dp[i-1][q[r]]<=dp[i-1][j]) r--;
q[++r]=j;
if(r>=l) dp[i][j]=max(dp[i][j],dp[i-1][q[l]]+f[i].b-abs(f[i].a-j));
//printf("dp:%d update\n",dp[i-1][q[l]]+f[i].b-abs(f[i].a-j));
}
//printf("#%d:(%d,%d)\n",i,l,r);
}
int res=-INF;
for(int i=1;i<=n;i++)
res=max(res,dp[m][i]);
printf("%d",res);
return 0;
}