[ARC070E] NarrowRectangles
首先考虑\(O(n^2)dp\),设\(dp_{i,j}\)表示前\(i\)个线段其右端点在\(j\)的最小代价,令\(len_i=R_i-L_i\)
\[dp_{i,j}=|R_i-j|+Min_{k=j-len_i}^{j+len_{i-1}}dp_{i-1,k} \]可以发现如果把\(dp\)抽象为函数,则\(Min_{k=j-len_i}^{j+len_{i-1}}dp_{i-1,k}\)显然在\(dp_{i-1}\)为凹函数的情况下同样为凹函数
而\(|R_i-j|\)同样为凹函数，则\(dp_i\)同样为凹函数
再模拟一下可以发现，\(dp_i\)的斜率为整数，且中间有连续的一段斜率为\(0\),设\(L,R\)一段斜率为\(0\)
\[Min_{k=j-len_i}^{j+len_{i-1}}dp_{i-1,k}=\left\{ \begin{aligned} dp_{i-1,k+len_{i-1}},k+len_{i-1}\le L\\ dp_{i-1,L},L-len_{i-1}\le k\le R+len_i\\ dp_{i-1,k-len_i},k-len_{i}\ge R \end{aligned} \right. \]可以发现斜率小于\(0\)左移\(len_{i-1}\),大于\(0\)右移\(len_i\),如果访问位置，可以用\(lazy\)标记
在考虑\(|R_i-j|\),反应到斜率就是\(<R_i\)的\(-1\),\(>R_i\)的\(+1\)(如果值域小一点其实可以用线段树)
然后考虑\(R_i\)的位置对函数的影响
\(R_i<L\),则原来斜率\(=0\)的会变为\(1\),而原来的\(-1\)便为0
如果我们维护每个\(<0\)斜率的右端点，\(>0\)斜率的左端点，那就可以每个斜率包括长度为\(0\)的都用堆维护
最后的答案我们如果知道斜率来算是可以直接求出来的
但如果维护每次斜率为\(0\)的答案，可以发现，每次取\(Min\)，\(L,R\)至少有一个点斜率不变，就可以把答案的取值设为两个端点中的一个即可
标签：函数,Min,NarrowRectangles,len,斜率,ARC070E,dp From： https://www.cnblogs.com/kid-magic/p/16834324.html