[DP记录]AT2347 [ARC070C] NarrowRectangles

command_block · 2021-05-12 08:21:54 · 个人记录

题意：有 n 个宽为 1 的木板从左到右排成一排，第 i 个木板覆盖了纵坐标 [l_i,r_i]。

现在可以上下移动这些木板，使得所有木板连接起来（有一点接触就算连接）。问最小的移动距离和。

------------ 先考虑 $\rm DP$。设 $f_{i,x}$ 表示处理了前 $i$ 个木板，最后一个木板的左端点放在 $x$ ，所需的最小移动距离和。显然，需要考虑的 $x$ 均为整数。不难写出转移方程： $$f_{i+1,x}=|x-l_{i+1}|+\min _{k\in[x-len_i,x+len_{i+1}]}f_{i,k}$$ $|x-l_i|$ 是下凸函数，凸函数的区间 $\rm min$ 也是凸函数，于是不难归纳证明 $f_{i,x}$ 是关于 $x$ 的凸函数。将 $f_{i,x}$ 改记为 $f_i(x)$。记 $f_i(x)$ 的最小值位置区间为 $[L_i,R_i]$ ，则可以写出转移方程： $$f_{i+1}(x)=|x-l_{i+1}|+\begin{cases}f_{i-1}(x+len_i)&(x<L_i-len_i)\\f_{i-1}(L_i)&(x\in[L_i-len_{i},R_i+len_{i+1}])\\f_{i-1}(x-len_{i+1})&(x>R_i+len_{i+1})\end{cases}$$ 这个方程相当于将 $f_i(x)$ 的左侧向左移动 $len_i$ ，右侧向右移动 $len_{i+1}$ ，然后加上一个绝对值函数。对于绝对值函数的处理，分三类讨论：用两个堆分别维护左右侧的凸壳，每个元素代表一个斜率变化 $1$ 的拐点。记加绝对值之前的函数，最小值区间为 $[L,R]$ ，记 $c=l_{i+1}$。 - **情况A** : $c\in [L,R]

最小值位置变为 l_{i+1} 。左侧斜率减一，右侧斜率加一，给左右两个堆各加入一个 c。

情况B : c<L

查看 L 左侧的第一段斜率为 -1 的区间，假设为 [T,L]。

则新的最小值区间为 [\max(c,T),L]。在左堆加入两个 c ，因为斜率变化了两次。
情况C : c>R

情况类似，查看 R 右侧的第一段斜率为 1 的区间，假设为 [R,T]。

则新的最小值区间为 [R,\min(c,T)]。在右堆加入两个 c。

需要给堆维护一个加法标记。

还要考虑如何求解答案。记 ans_i 为 f_{i}(x) 的最小值，则：

情况A : 最小值不变。
情况B : 最小值加上 L-c
情况C : 最小值加上 c-R

复杂度 O(n\log n)。

#include<algorithm>
#include<cstdio>
#include<queue>
#define ll long long
#define MaxN 100500
using namespace std;
int n;ll len[MaxN];
priority_queue<ll> ql;
priority_queue<ll,vector<ll>,greater<ll> > qr;
int main()
{
  ll x,tl=0,tr=0,ans=0;
  scanf("%d%lld%lld",&n,&x,&len[1]);
  len[1]-=x;ql.push(x);qr.push(x);
  for (int i=2;i<=n;i++){
    scanf("%d%d",&x,&len[i]);
    len[i]-=x;
    tl-=len[i];tr+=len[i-1];
    ll L=ql.top()+tl,R=qr.top()+tr;
    if (L<=x&&x<=R){ql.push(x-tl);qr.push(x-tr);}
    else if (x<L){
      ans+=L-x;
      ql.pop();qr.push(L-tr);
      ql.push(x-tl);ql.push(x-tl);
    }else {
      ans+=x-R;
      qr.pop();ql.push(R-tl);
      qr.push(x-tr);qr.push(x-tr);
    }
  }printf("%lld",ans);
  return 0;
}