一条街道有(n)个区域。 从左到右编号为(1)到(n)。 相邻区域之间的距离为(1)。
在节日期间，有(m)次烟花要燃放。 第(i)次烟花燃放区域为(a_i) ，幸福属性为(b_i)，时间为(t_i)。(t_i leqslant t_{i+1})
如果你在第(i)次烟花发射时在(x（1leqslant x leqslant n）)处，你将获得幸福值(b_i - | a_i - x |) （请注意，幸福值可能是负值）。
你可以在单位时间间隔内移动最多(d)个单位，但禁止走出主要街道。 此外，您可以在初始时刻（时间等于(1)时）处于任意区域，并希望最大化从观看烟花中获得的幸福总和。
输出最大的幸福总和。
题目解答
本题是单调队列优化(DP)的经典题目。
设(dp[i][j])表示第(i)次烟花燃放时你位于(j)处所能获得的最大的幸福总和。
而第(i-1)次烟花燃放到第(i)次烟花燃放所能移动的最大距离为(h=(t_i-t_{i-1})*d)。
所以该次燃放后可能获得的幸福总和由上一次位于([j-h,j+h])处的(2h+1)种情形得到。
且(dp[i][j]=max{dp[i-1][k]+b[i]-|a[i]-j|} quad kin [j-h,j+h])
即(dp[i][j]=max{dp[i-1][k]}+b[i]-|a[i]-j| quad kin [j-h,j+h])
故对于(jin[1,n]) ，要求(dp[i][j])的值只要求解(dp[i-1])数组位于([j-h,j+h])的最大值，而求解这一步可以用单调队列解决，复杂度(O(n))，即可求解完(dp[i])数组。
又发现(dp[i])数组的求解只与(dp[i-1])数组有关，故这一维可以滚动处理。
(dp[s1])表示源状态，(dp[s2])表示将求解状态，求解完交换(s1)，(s2)即可。(s1,s2in{0,1})
单调队列处理部分
我的代码采用双端队列(deque)处理，较为简洁。
(deque)存储位置编号
其中(deque)中从队首到队尾，位置编号严格增加，该位置源状态(dp)源状态值严格减少；
处理位置(i)（采用代码中变量意义）时，将还未处理的小于(i+h)的位置依次入队尾（可能有些元素会被赶出队尾，因为它们不可能再被使用到），再将小于(i-h)的位置依次出队头。则队首所在位置便是源状态位于([i-h,i+h])的最大值，即可得到现状态。
源代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=15e4+10;
LL q,m,d,n,s1=0,s2=1;
LL dp[2][maxn];
int main(){
scanf("%lld%lld%lld%",&n,&m,&d);
LL a,b,t,qian_t=1;
while(m--){
scanf("%lld%lld%lld%",&a,&b,&t);
LL h=(t-qian_t)*d;
qian_t=t;
deque<int> qu;
for(int i=1,j=1;i<=n;i++){
for(;j<=i+h&&j<=n;j++){
while(!qu.empty()&&dp[s1][qu.back()]<=dp[s1][j])qu.pop_back();
qu.push_back(j);
}
while(!qu.empty()&&qu.front()<i-h)qu.pop_front();
dp[s2][i]=dp[s1][qu.front()]+b-abs(i-a);
}
swap(s1,s2);
}
LL maxm=dp[s1][1];
for(int i=2;i<=n;i++){
if(dp[s1][i]>maxm)maxm=dp[s1][i];
}
printf("%lld",maxm);
}
结束语
欢迎留言！你们的支持与推荐是博主发展的动力XD.