【ARC073F】Many Moves

题目

一个显然的\(dp\)，设\(dp_{i,j}\)表示其中一个棋子在\(x_i\)点，另一个棋子在\(j\)点的最小花费

显然\(dp_{i,j}\)有两种转移

第一种是把\(x_i\)上的棋子移到\(x_{i+1}\)，那么那么就是\(dp_{i+1,j}=\min(dp_{i,j}+|x_{i+1}-x_i|)\)

第二种就是把\(j\)上的棋子移动到\(x_{i+1}\)，那么就是\(dp_{i+1,x_i}=\min(dp_{i,j}+|j-x_{i+1}|)\)

这是\(O(nQ)\)的，考虑优化

发现第一种转移形式非常固定，于是直接整体\(dp\)。第一种转移其实就是全局加，我们维护一个加法标记就可以了。

第二种转移都是转移到\(dp_{i+1,x_i}\)，绝对值看起来比较讨厌，考虑将绝对值拆开，当\(j\geq x_{i+1}\)时，\(dp_{i+1,x_i}=dp_{i,j}+j-x_{i+1}\)；当\(j\leq x_{i+1}\)时，\(dp_{i+1,x_i}=dp_{i,j}-j+x_{i+1}\)，于是考虑直接使用线段树来维护\(dp_{i,j}+j\)和\(dp_{i,j}-j\)的最小值，查一下这两个区间就能转移了。

代码

#include<bits/stdc++.h>

#define re register

#define LL long long

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const LL inf=1e15;

const int maxn=2e5+5;

int l[maxn<<2],r[maxn<<2];LL mx[maxn<<2][2],tag;

int pos[maxn],d[maxn],n,A,B,Q;

inline LL min(LL a,LL b) {return a<b?a:b;}

void build(int x,int y,int i) {

	l[i]=x,r[i]=y;mx[i][0]=mx[i][1]=inf;

	if(x==y) {pos[x]=i;return;}

	int mid=x+y>>1;

	build(x,mid,i<<1),build(mid+1,y,i<<1|1);

}

void change(int x,LL v,int o) {

	x=pos[x];mx[x][o]=min(v,mx[x][o]);x>>=1;

	while(x) mx[x][o]=min(mx[x][o],v),x>>=1;

}

LL query(int x,int y,int i,int o) {

	if(x<=l[i]&&y>=r[i]) return mx[i][o];

	int mid=l[i]+r[i]>>1;LL now=inf;

	if(x<=mid) now=min(now,query(x,y,i<<1,o));

	if(y>mid) now=min(now,query(x,y,i<<1|1,o));

	return now;

}

inline LL ABS(LL x) {return x>=0?x:-x;}

int main() {

	n=read(),Q=read(),A=read(),B=read();

	for(re int i=1;i<=Q;i++) d[i]=read();

	build(1,n,1);

	change(A,ABS(d[1]-B)+A,0);change(A,ABS(d[1]-B)-A,1);

	change(B,ABS(d[1]-A)+B,0);change(B,ABS(d[1]-A)-B,1);

	for(re int i=2;i<=Q;i++) {

		LL x=query(d[i],n,1,0)-d[i],y=query(1,d[i],1,1)+d[i];

		x=min(x,y);

		LL a=min(mx[pos[d[i-1]]][0]-d[i-1],mx[pos[d[i-1]]][1]+d[i-1]);

		if(x<a+ABS(d[i]-d[i-1])) {

			x+=tag;tag+=ABS(d[i]-d[i-1]);x-=tag;

			change(d[i-1],x+d[i-1],0),change(d[i-1],x-d[i-1],1);

		}

		else tag+=ABS(d[i]-d[i-1]);

	}

	LL ans=inf;

	for(re int i=1;i<=n;i++) ans=min(ans,mx[pos[i]][1]+i);

	printf("%lld\n",ans+tag);

	return 0;

}