CF327C
学DP优化了。
设 \(f_{i,j}\) 表示在第 \(i\) 个时间，在第 \(j\) 个位置时的最大答案。
容易写出朴素的状态转移方程。
\[f_{i,j}=max(f_{i,k}+b_i-\left |a_i-j\right| )
\]
这里的 \(k\) 有一定的范围，
\[j-(t_i-t_{i-1})*d\le k\le j+(t_i-t_{i-1})*d
\]
发现要枚举 \(i,j,k\) 可以考虑去掉 \(k\)，显然当 \(i,j\) 确定的时候，状态转移方程可以变形成如下形式。
\[f_{i,j}=max(f_{i,k})+b_i-\left |a_i-j\right|
\]
我们知道 \(f_{i,k}\) 是连续的一段，也就是区间RMQ问题，考虑单调队列优化。
数据要开long long，然后空间会炸，滚一下就行了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=150005,M=305;
int n,m,t[M],b[M],a[M],q[N],d,head,tail,f[2][N];
signed main(){
memset(f,-0x3f,sizeof(f));
n=read(),m=read();d=read();
for(int i=1;i<=m;++i)a[i]=read(),b[i]=read(),t[i]=read();
int zc=0;
for(int i=1;i<=n;++i)
f[zc][i]=b[1]-abs(a[1]-i);
for(int i=2;i<=m;++i,zc^=1){
head=1,tail=0;
for(int j=1;j<=std::min(n,(t[i]-t[i-1])*d+1);++j){
while(head<=tail&&f[zc][j]>=f[zc][q[tail]])tail--;
q[++tail]=j;
}
f[zc^1][1]=f[zc][q[head]]+b[i]-abs(a[i]-1);
for(int j=2;j<=n;++j){
int l=std::max(j-(t[i]-t[i-1])*d,1ll),r=std::min(j+(t[i]-t[i-1])*d,n);
while(head<=tail&&f[zc][r]>=f[zc][q[tail]])tail--;
q[++tail]=r;
if(q[head]<l)head++;
f[zc^1][j]=f[zc][q[head]]+b[i]-abs(j-a[i]);
}
}
long long ans=-2e9;
for(int i=1;i<=n;++i)ans=std::max(ans,f[zc][i]);
std::cout<<ans;
}