本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-16 16:09:32

题意

有 $n$ 个城市，$m$ 个依次进行的活动，初始有无穷多的钱且位于城市 $1$。在 $T_i$ 城市参加第 $i$ 个活动可以获得 $P_i$ 的钱，而从 $i$ 城市移动到 $j$ 城市需要花费 $C\times\left|i-j\right|$ 的钱，求最多能净赚多少钱。

思路

考虑动态规划解决。

设 $f_i$ 为最终停在第 $i$ 个城市能赚的最大钱数，有初值 $f_1=0$。由于要取最大值，将所有 $i\neq 1$ 的 $f_i$ 赋为负无穷。

接着需要依次处理每个活动，每次有转移式 $f_{T_i}=\max(f_{T_i},P_i+\max\limits_{j=1}^{n}(f_j-C\times\left|T_i-j\right|))$，其中要保证 $f_j$ 不为负无穷，否则没有意义。

如果每次转移时暴力地遍历整个 $f$ 数组，时间复杂度为 $O(mn)$，必然超时，需要更快速地求出转移式的第二项。

考虑使用数据结构优化时间复杂度，发现如果能把第二项中含 $j$ 的部分看成整体，就能用线段树维护最大值来解决。

那么需要通过分讨拆掉绝对值，因此化简得：

• 当 $j\leq T_i$ 时，$f_j-C\times\left|T_i-j\right|=-C\times T_i+f_j+C\times j$。
• 当 $j\geq T_i$ 时，$f_j-C\times\left|T_i-j\right|=C\times T_i+f_j-C\times j$。

发现两个式子中含 $i$ 的部分在每次转移时都是定值，因此当含 $j$ 的部分最大时，整个式子也最大。

因此可以用线段树分别维护 $f_j+C\times j$ 和 $f_j-C\times j$ 的区间最大值，每次转移时分别求 $\left[ 1,T_i\right]$ 和 $\left[T_i,n\right]$ 的最大值，再进行更新。

形式化地，先求 $k=\max(-C\times T_i+\max\limits_{j=1}^{T_i}(f_j+C\times j),C\times T_i+\max\limits_{j=T_i}^{n}(f_j-C\times j))$，再更新$f_{T_i}=\max(f_{T_i},P_i+k)$。

时间复杂度为 $O(m \log n)$。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=1e18;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0',ch=getchar();}
	return s*w;
}
int n,c,m,ans,ct=1,f[N];
struct nod
{
	int l,r,w[2];
}a[N*2];
void pushup(nod &u,nod lc,nod rc)
{
	u.w[0]=max(lc.w[0],rc.w[0]),u.w[1]=max(lc.w[1],rc.w[1]);
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		if(l==1) a[u].w[0]=c,a[u].w[1]=-c;
		else a[u].w[0]=a[u].w[1]=-inf;
		return;
	}
	int mid=(l+r)\/2;
	a[u].l=++ct,build(ct,l,mid);
	a[u].r=++ct,build(ct,mid+1,r);
	pushup(a[u],a[a[u].l],a[a[u].r]);
}
void change(int u,int l,int r,int p)
{
	if(l==r)
	{
		a[u].w[0]=f[l]+l*c,a[u].w[1]=f[l]-l*c;
		return;
	}
	int mid=(l+r)\/2;
	if(p<=mid) change(a[u].l,l,mid,p);
	else change(a[u].r,mid+1,r,p);
	pushup(a[u],a[a[u].l],a[a[u].r]); 
}
nod query(int u,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr) return a[u];
	int mid=(l+r)\/2;
	if(rr<=mid) return query(a[u].l,l,mid,ll,rr);
	if(ll>mid) return query(a[u].r,mid+1,r,ll,rr);
	nod res;
	pushup(res,query(a[u].l,l,mid,ll,rr),query(a[u].r,mid+1,r,ll,rr));
	return res;
}
signed main()
{
	n=read(),c=read(),m=read();
	for(int i=2;i<=n;i++) f[i]=-inf;
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int x=read(),w=read();
		int ta=query(1,1,n,1,x).w[0],tb=query(1,1,n,x,n).w[1];
		if(ta!=-inf) ta-=x*c;
		if(tb!=-inf) tb+=x*c;
		int ts=w+max(ta,tb);
		if(ts>f[x]) f[x]=ts,change(1,1,n,x);
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}