ARC070E NarrowRectangles
题意：平面上有 \(n\) 个矩形，左下角点坐标为 \((l_i,i-1)\)，右上角点坐标为 \((r_i,i)\)。每次把一个矩形沿着横轴方向移动一个长度单位，求移动多少次使得任意两个相邻矩形存在交点。
\(1\le n\le 10^5,\space 1\le l_i< r_i\le 10^9\)
考虑最简单的 dp，设 \(f[i,j]\) 表示处理了前 \(i\) 个矩形，并且第 \(i\) 个矩形左边界移动到了 \(j\) 位置的最小代价。
有转移：
\[f[i,j]=|j-l_i|+\min_{j-len_{i-1}\le k\le j+len_i}\{f[i-1,k]\} \]一个很巧妙的 trick：考虑 \(|j-l_i|\) 是凸函数，并且凸函数的区间平移最小值还是凸函数，可以归纳证明 \(f[i,]\) 也是凸函数。
设 \(f_i(x)\) 为 \(f[i,]\) 在图像上的函数，设 \(L,R,v\) 为 \(f_{i-1}(x)\) 上最小值的区间，以及对应的最小值，那么：
\[f_i(x)=|x-l_i|\begin{cases} f_{i-1}(x+len_i) & x<L-len_i \\ v & L-len_i\le x\le R+len_{i-1} \\ f_{i-1}(x-len_{i-1}) & x>R+len_{i-1} \end{cases} \] 标签：练习题,le,14,凸函数,len,最小值,2024.3,矩形,dp From： https://www.cnblogs.com/Sktn0089/p/18073087