[DP记录]AT2558 [ARC073D] Many Moves

**题意** ： 在一行中有 $n$ 个格子，编号为 $1\sim n$ 。 有 $2$ 颗棋子，初始时分别位于位置 $a$ 和 $b$ 。 按顺序给出 $q$ 个要求： - 给出位置 $x_i$ ，要求将两个棋子中任意一个移动到位置 $x_i$ 。 就是说将棋子从 $x$ 位置移动到 $y$ 位置需要花费 $|x-y|$ 秒。允许两棋子在同一个位置上。 问满足所有要求所需的最小时间。 $n,q\leq 2\times 10^5$ ，时限$\texttt{2s}$。 ------------ 考虑 $\rm DP$ ，记 $dp[i][x][y]$ 为 ： 在处理完前 $i$ 个要求后，两个棋子的位置分别为 $x,y$ ，所需的最小时间。 可以发现，当处理完第 $i$ 个要求时，必定有一个棋子在 $x_i$ 处，故状态可以简化为 ： $dp[i][y]$ 表示在处理完前 $i$ 个要求后，一个棋子在 $x_i$ 处，另一个在 $y$ 处，所需的最小时间。 转移如下 : $$ \begin{aligned} {\color{white}\Big|}dp[i+1][y]&=dp[i][y]+|x_i-x_{i+1}|\\ dp[i+1][x_{i}]&=\min dp[i][y]+|y-x_{i+1}|\\ &=\min\Big\{\min_{y\in[1,x_{i+1}]}x_{i+1}+dp[i][y]-y,\ \min_{y\in(x_{i+1},n]}-x_{i+1}+dp[i][y]+y\Big\}\\ \end{aligned} $$ 只需维护 $dp[i][y]-y,dp[i][y]+y$ （$±y$ 也容易写进一次函数）的区间 $\min$ 即可处理第二种转移。 第一种转移不便维护，记 $s_i=\sum\limits_{k=1}^{i-1}|x_i-x_{i+1}|$ ，改为记录 $dp'[i][y]=dp[i][y]-s_i$。 这样，第一种转移对 $dp'[i][y]$ 是没有影响的。 第二种转移中额外减去 $|x_{i}-x_{i+1}|$ 即可。 使用（两颗）线段树维护，复杂度 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 200500 using namespace std; const ll INF=1ll<<60; int n,to,wfl,wfr;ll wfc,ret; struct SGT { ll a[MaxN<<2]; void build(int l,int r,int u) { a[u]=INF; if (l==r)return ; int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); } inline void up(int u) {a[u]=min(a[u<<1],a[u<<1|1]);} void chg(int l,int r,int u) { if (l==r){a[u]=wfc;return ;} int mid=(l+r)>>1; if (to<=mid)chg(l,mid,u<<1); else chg(mid+1,r,u<<1|1); up(u); } void chg(int p,ll c) {to=p;wfc=c;chg(1,n,1);} void qry(int l,int r,int u) { if (wfl<=l&&r<=wfr) {ret=min(ret,a[u]);return ;} int mid=(l+r)>>1; if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } ll qry(int l,int r) {wfl=l;wfr=r;ret=INF;qry(1,n,1);return ret;} void dfs(int l,int r,int u) { if (l==r){ret=min(ret,a[u]-l);return ;} int mid=(l+r)>>1; dfs(l,mid,u<<1); dfs(mid+1,r,u<<1|1); } }T1,T2; int m,x[MaxN],y; int main() { scanf("%d%d%d%d",&n,&m,&x[0],&y); T1.build(1,n,1);T2.build(1,n,1); T1.chg(y,y);T2.chg(y,-y); for (int i=1;i<=m;i++){ scanf("%d",&x[i]); ll sav=min(x[i]+T2.qry(1,x[i]),-x[i]+T1.qry(x[i],n)); sav=sav-(x[i]>x[i-1] ? x[i]-x[i-1] : x[i-1]-x[i]); T1.chg(x[i-1],sav+x[i-1]);T2.chg(x[i-1],sav-x[i-1]); } ret=INF;T1.dfs(1,n,1); for (int i=1;i<=m;i++) ret+=(x[i]>x[i-1] ? x[i]-x[i-1] : x[i-1]-x[i]); printf("%lld",ret); return 0; } ```