题意

前言

学习一个新的算法，总是要仔细考虑一些深入的问题

题解

首先清楚单调队列是一个主要用来优化 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;
}

【ybtoj】【单调队列】燃放烟火

原文：https://www.cnblogs.com/conprour/p/15266845.html