斜率优化---感谢此文让我彻底弄懂斜率优化

若深究斜率优化,有重重疑惑,建议学习此文.

阅遍网上大量 斜率优化 文章,唯独此文,将本人疑惑一一解清,作为之前几乎不转载的作者,今日,郑重将此文转载,原文来自https://www.cnblogs.com/terribleterrible/p/9669614.html有删改。

在https://www.luogu.org/problemnew/solution/P3195?page=3作者: Brioche 更新时间: 2018-09-18 17:09 发现此文,埋没了，实在可惜。

[HNOI2008]玩具装箱TOY   //在线测评地址https://www.luogu.org/problemnew/show/P3195

"这是一道经典的斜率优化入门题,就用这题来作个总结好了." 这道题用到的是单调队列(我只会这玩意儿)的斜率优化. 我们整理一下题意会发现它的状态转移方程就是下面这东西:

dp[i]=min(dp[j]+(sum[i]+i−sum[j]−j−L−1)^2),i>j

上面这张图讲得已经很清楚了. 我们如果把含j的相关变量都看成点的坐标的话,此时我们要做的就是尽量让截距更小. 怎么让截距最小呢?难道一个一个比较吗? 我们再来看下面这张图:

上面三个点是我们可供选择的三个点,这条直线就是我们就是要使这条一直斜率的截距最小. 高中数学学线性规划的时候我们都知道,显然是选途中的B点. 那么对于这一条直线,我们根据斜率和坐标可以计算截距,从而得到dp值. 那剩下两个点呢? 对于A点,我们是不是可以丢掉它了?是的,由于我们的斜率是不断增大的,A点是不可能用来转移后面的状态了,所以把它剔除. 还有C点,当斜率到达一定大小,例如下图:

此时我们就要用到C,而B又可以剔除. 于是我们只要维护一个凸包,而且这个凸包相邻两个点连的斜率要大于当前这条线的斜率.就像刚刚这个例子一样.一旦最左端的一个点和次左端的点的连线要小于当前的斜率了,就把最左端的点剔除. 这样每次遇到新的直线,直接拿最左端的点(队头)来转移,加入一个新点就加到最右边(队尾),因为横坐标也是递增的.再加入这个点之前,我们一定要保证下凸的性质,例如下面这个例子:

B显然要被剔除. 为什么一定维护凸包呢?为什么一定是弹掉B.C为什么更优呢?自己想象一下,一条直线斜率大于CG的直线从下面平移上来,走啊走,最后一定会在C这里停下.如果是一条斜率小于GC大于GF的,显然会在G停下,这样B

就没有人和用武之地了.

在这里我们总结一下,单调队列斜率优化的步骤: 1.弹队头,就是最左边的点. 2.放直线,算答案,得到当前状态的答案,得到新的待加入的点. 3.弹队尾,把插入新点之后不合法的点弹掉.最后加入新点就好了.

//P3195 [HNOI2008]玩具装箱TOY //在线测评地址https://www.luogu.org/problemnew/show/P3195 //有思路，但数学式子推得很乱， //翻看https://www.cnblogs.com/Paul-Guderian/p/7259491.html推导 //发现，一个换元，想到了，但没付出实践;一个L++，确实没想到。就这两下，式子变得简单多了。 //dp[j]+(sum[j]+j+L)*(sum[j]+j+L)-(dp[k]+(sum[k]+k+L)*(sum[k]+k+L)     return (sum[j]+j+L)-(sum[k]+k+L); } int main(){     LL i,u;     scanf("%lld%lld",&n,&L);     L++,sum[0]=0;     for(i=1;i