数据结构优化DP--Pieces

题目： 有 $N$个格子排成一行。这些格子从左到右标号为 $1$~$N$。 你有两个棋子，开始分别放在$A$号格子和$B$号格子里。你将要按照接收的顺序执行$q$个以下形式的请求： 给定一个正整数 $x$，选择两个棋子中的一个，把它移动到$x$号格子里。 把一个棋子移动一格需要一秒钟的时间。也就是说，把一个棋子从$x$号格子移到$y$号格子需要$|x-y|$秒的时间。 你的目标是在尽量短的时间内执行完所有的请求。 你只能为了回应请求而移动棋子，并且你不能同时移动两个棋子，此外你不能更改接收请求的顺序。但是允许在某个时刻，两个棋子在同一个格子里。

solution: 直接贴上图吧$QAQ$ 数据结构优化$DP$，$get$新姿势

放代码：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 200005 #define LL long long #define int LL using namespace std; int n,q,A,B,tag,f[maxn],g[maxn],dp[maxn],x[maxn],ans; inline int rd(){ int x=0,f=1;char c=' '; while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar(); while(c<='9' && c>='0') x=x*10+c-'0',c=getchar(); return x*f; } inline void add(int x){ for(int i=x;i<=n;i+=i&-i) f[i]=min(f[i],dp[x]-x);//前缀 for(int i=x;i;i-=i&-i) g[i]=min(g[i],dp[x]+x);//后缀 } inline int query_pre(int x){ int sum=1LL<<60; for(int i=x;i;i-=i&-i) sum=min(sum,f[i]); return sum; } inline int query_beh(int x){ int sum=1LL<<60; for(int i=x;i<=n;i+=i&-i) sum=min(sum,g[i]); return sum; } signed main(){ freopen("pieces.in","r",stdin); freopen("pieces.out","w",stdout); n=rd(); q=rd(); A=rd(); B=rd(); for(int i=1;i<=q;i++) x[i]=rd(); memset(dp,0x3f,sizeof dp); memset(f,0x3f,sizeof f); memset(g,0x3f,sizeof g); dp[A]=abs(x[1]-B); dp[B]=abs(x[1]-A); add(A); add(B); for(int i=2;i<=q;i++){ int dis=abs(x[i]-x[i-1]);//当前位置不等于x[i-1] dp[x[i-1]]=min(query_pre(x[i])+x[i],query_beh(x[i])-x[i])-dis;//当前位置等于x[i-1] add(x[i-1]); tag+=dis; } ans=1LL<<60; for(int i=1;i<=n;i++) ans=min(ans,dp[i]); printf("%lld\n",ans+tag); return 0; }