一、简单的复习 我在这里给出一个式子，，这是绝大部分dp式子的最基本的模型，每一道题可能只是将改为，或者是将calc中的东西更改一下，大家思考一下是不是这样的。 如果当calc之中的每一项都只含有或者是，并且这两个字母没有相乘的情况我们就可以用单调队列，这个不难理解，举个例子，像下面的这个式子：，就可以用单调队列维护，因为整个式子之中只有关于的单独项和关于的单独项。 但是像这样的式子就不可以了：，因为这个式子展开后就会出现关于的式子乘上关于的式子。像这样的式子就是斜率优化的适用范围。 二、斜率优化 像斜率优化这样知识点需要一道例题来进行讲解。下面我们来看一道经典的例题。 1.列方程 我们先想这道题的dp式子，先不管时间复杂度的问题。 这个式子应该很好想：，我们来分析一下时间复杂度：。 想一下优化，我们是不是可以将求和部分写成前缀和的形式？将的部分化成。这样我们就可以将式子转化成，这样的话时间复杂度就降低成为。时间是更低了，但是还是过不了啊，这是我们就要等价地变换式子，使其成为y=kx+b的形式，这个形式就是斜率优化的核心。 2.转化式子 令 3.分析式子 观察上面的式子，我们发现这个式子十分像一种函数，y=kx+b，可能大家会有疑问，这个式子和直线的表达是有什么形似之处呢？ 我们将这个部分看做一个整体记为，这个部分可以看成一个整体的条件是：这个整体中的所有部分都是已求出的，并且当知道和之后可以求出。显然这个整体满足。同理我们将和这两个部分也分别看做整体，并分别记为、。这样式子就化为。 下一步，我们建立以个平面直角坐标系，这个平面直角坐标系中的每一个点的坐标（，）​都对应的是上面式子中的​和​，这样我们就能够将每一个与​有关的东西处理完事之后标到平面直角坐标系之中。每一个点的坐标表成，（）​，可能有人会问为什么纵坐标没有了​，并且横坐标没有了​，这个问题下面会解答，请稍作等待。 如果我们想用来转移的话，就要让斜率为的直线过点，（），并且此时直线的截距就是新的，因为为这条直线的。再看下面的图解，我们将求过的点都标到平面直角坐标系中，我们可以发现，我们想过的这个点一定在我们维护的大圆包上，像点2这样的点就不能被用来更新，因为过点3所得截距，一定比过点2所得截距小，那么我们能发现当点3求出之后，只要比较一下，点2和点3形成的直线的斜率和点1和点2形成的直线的斜率，如果2、3形成的比1、2形成的要小，那么3号点一定比2号点更优。我们再看，假设下图之中已经维护好1到5的所有点，那么就会出现这样的大圆包。我们用求出6的点的直线去和这些点相交，我们发现只有点4在当前直线上时能使截距最小（画一画图就能发现是过点4时，直线的截距最小），根据是由点4转移，我们可以发现，当两个点1、3的斜率小于的时候，横坐标小的点一定不能用来转移，同理斜率大于的两个点，横坐标大的也不能够用来转移，这个性质是不是很好？ 根据上面我们发现的式子，我们可以维护一个类似于单调队列的队列来维护我们的大圆包。但是这个大圆包具体怎么维护呢？我们先看如何求斜率。如果给你直线上的两个点，我想大家一定会求斜率。就是两点的纵坐标相减的差除上两点的横坐标相减的差。这里也就解释了，为什么上文中的纵坐标没有了，因为两式相减时是相同的，从而也就是相同的，所以相减时就将其减掉了，因此不用出现在纵坐标之中。同理在相减时我们的横坐标也不需要。 double re_x(int i){return s[i];} double re_y(int i){return f[i]+(s[i]+l)*(s[i]+l);} double re_k(int i,int j){return (re_y(j)-re_y(i))/(re_x(j)-re_x(i));} 会求斜率了，我们再来看怎么维护大圆包，我们发现当队列中最后一个的点和队列中倒数第二个点的产生斜率大于最后一个点和新产生的点产生的斜率，那么结尾就要弹出队列，这个用一个循环就能够解决，最后再将新产生的点放在结尾。这个实现十分像单调队列的实现。 int main() { while(head #define N 50001 int n,l,head,tail; long long f[N],s[N],q[N]; double re_x(int i){return s[i];} double re_y(int i){return f[i]+(s[i]+l)*(s[i]+l);} double re_k(int i,int j){return (re_y(j)-re_y(i))/(re_x(j)-re_x(i));} int main() { scanf("%d%d",&n,&l); for(int i=1;i<=n;i++) scanf("%lld",&s[i]),s[i]+=s[i-1]; for(int i=1;i<=n;i++) s[i]+=i; q[tail]=0; for(int i=1;i<=n;i++) { while(head

关键字：