[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\)至少有一个点斜率不变，就可以把答案的取值设为两个端点中的一个即可
原文地址：http://www.cnblogs.com/kid-magic/p/16834324.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
