[DP记录]AT2347 [ARC070C] NarrowRectangles

**题意** ： 有 $n$ 个宽为 $1$ 的木板从左到右排成一排，第 $i$ 个木板覆盖了纵坐标 $[l_i,r_i]$。 现在可以上下移动这些木板，使得所有木板连接起来（有一点接触就算连接）。问最小的移动距离和。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 先考虑 $\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)$。 ```cpp #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; } ```