题意：有n个点，其中m个要放烟花。每个放烟花的点有属性b[i]，放的时间t[i]和位置a[i]。假设放烟花的时候你在位置x，那么可以获得快乐b[i]-|x-a[i]|。你走来走去地看烟花，起始位置任意，每秒最多能走d个点。求最多能获得多少快乐。
解：先设dp[i][j]为放到第i个烟花，你在位置j，能获得的最大欢乐值。不难推出 dp[i][j]=max(dp[i-1][k]+b[i]-|a[i]-j|)， k 属于 [j-d, j+d]。直接转移时间复杂度会炸，用线段树优化也会，考虑到每次要用的区间都向右移了一格，且b[i]-|a[i]-j|是常数，可以用单调队列求dp[i-1][k]的最大值。当前点两边的值都能取，因此做两遍。然后优化空间，滚动一下数组。
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxx 150005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 2520
ll a[305],b[305],t[305];
ll dp[2][maxx];
int q[maxx]={0};
signed main() {
int n,m,d;
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=m;i++){
scanf("%I64d%I64d%I64d",&a[i],&b[i],&t[i]);
}
memset(dp,-0x3f3f3f3f,sizeof dp);
for(int i=1;i<=n;i++){
dp[1][i]=b[1]-abs(a[1]-i);
}
int c=0;
for(int i=2;i<=m;i++){
ll len=(t[i]-t[i-1])*d;
int l=1,r=0;
for(int j=1;j<=n;j++){
while(l<=r&&q[l]<j-len) l++;
while(l<=r&&dp[1-c][q[r]]<dp[1-c][j]) r--;
q[++r]=j;
dp[c][j]=dp[1-c][q[l]]+b[i]-abs(a[i]-j);
}
l=1,r=0;
for(int j=n;j>=1;j--){
while(l<=r&&q[l]>j+len) l++;
while(l<=r&&dp[1-c][q[r]]<dp[1-c][j]) r--;
q[++r]=j;
dp[c][j]=max(dp[c][j],dp[1-c][q[l]]+b[i]-abs(a[i]-j));
}
c=1-c;
}
ll ans=-1e18;
for(int i=1;i<=n;i++){
ans=max(ans,dp[1-c][i]);
}
printf("%I64d\n",ans);
return 0;
}
//dp[i][j] max value of the i th firework, in the j th section
//dp[i][j]=max(dp[i-1][k]+b[i]-|a[i]-j|), k is in [j-d, j+d]
View Code
标签：Watching,int,ll,Fireworks,305,烟花,Fun,dp,define From： https://www.cnblogs.com/capterlliar/p/16900653.html