ABC353G 题解
KSCD_
·
·
题解
题意
有 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$ 数组，时间复杂度为 $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)$。
### 代码
```cpp
#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;
}
```