这里是斜率优化的具体操作和证明，恩，顺便附上一个例子，APIO2010第一题commando/特别行动队的解题思路。
前言：
对于一个动态规划模型f[i]=max{f[j]+g(j,i)}（这里只讨论max，min的可以想成-max{什么什么}）。
我们称对于阶段i决策x的价值为value(x)=f[x]+g(x,i)。
那么如果value(j)-value(k)>0，我们就说j比k优。
如果j<k时，value(j)-value(k)>0可以化成K(j,k)>H(i)的形式（这时K(j,k)>H(i)等价于j比k优），且H(i)是单调递增的，我们就可以用斜率优化了。
我们需要维护一个单调队列使得K(队中相邻的两个决策)递增。
具体操作：
Line
0 |Type f[XX..YY];
1 |Deque q;
2 |f[边界]:=边界值;
3 |q.push_back(边界);
4 |
5 |for i:=XX to YY do
6 |begin
7 | while q中至少有两个决策 and K(队首,队首的后一个)<=H(i) do q.pop_front();
8 | f[i]=value(队首);
9 | while q中至少有两个决策 and K(队尾的前一个,队尾)>=K(队尾,i) do q.pop_back();
10 | q.push_back(i);
11 |end;
证明（我用《算法导论》中的循环不变式来证明）：
初始化：在0到3行的代码执行后，f[边界]=边界值，队中没有相邻的两个决策，所以显然是正确的。
保持：
/*开始*/
在5到11行代码中，涉及到三个操作，除去队首无用决策（第7行），计算f[i]（第8行），除去队尾无用决策并加入决策i（第9到10行），我们分别证明。
1.除去队首无用决策
由于K(队中相邻的两个决策)在这次操作前是递增的，所以执行第7行代码后，K(队中相邻的两个决策)>H(i)，即队中前一个元素比后一个元素优，或者q中只有一个决策（而它显然最优），又因为H(i)递增，所以被pop掉的决策总是前一个没有后一个优，并且都没有新的队首优，所以pop他们是正确的。
综上所述，这一步是正确的。
2.计算f[i]
由于除去队首无用决策后，队中前一个元素比后一个元素优，所以最优的决策显然在队首，所以f[i]:=value(队首)这个操作显然正确。
3.除去队尾无用决策并加入决策i
如果q中只有一个决策，那么我们将i直接加入队尾，显然K(队中相邻的两个决策)是递增的。
如果q中有多于一个决策，那么如果K(队尾的前一个,队尾)>=K(队尾,i)，那么在某个阶段i’:
1)如果K(队尾的前一个,队尾)>=H(i’)>=K(队尾,i)，那么”队尾”没有”队尾的前一个”优，也没有”i”优，所以”队尾”不可能成为最优的决策，我们pop它，显然正确；
2)如果K(队尾的前一个,队尾)>=K(队尾,i)>=H(i’)，那么”队尾”没有”队尾的前一个”优，只是比”i”优，所以”队尾”不可能成为最优的决策，我们pop它，显然正确；
3)如果H(i’)>=K(队尾的前一个,队尾)>=K(队尾,i)，那么”队尾”没有”i”优，只是比”队尾的前一个”优，所以”队尾”不可能成为最优的决策，我们pop它，显然正确。
综上所述，如果K(队尾的前一个,队尾)>=K(队尾,i)，pop队尾是一个正确的举动。
如果K(队尾的前一个,队尾)<K(队尾,i)，那么我们停止while，然后q.push_back(i)，这时保持了K(队中相邻的两个决策)的单调性，是我们想要的，所以正确。
/*结束*/
终止：当算法结束后，f[YY]已经求出，即我们需要的最优值已经求出，这意味这算法是正确的。
例子（APIO2010第一题commando/特别行动队）：
恩，输入n,a,b,c,x[1..n]。
预处理sum[0]:=0，sum[i]:=sum[i-1]+x[i]。
动规方程是f[i]=max{f[j]+g(j,i)}，这里g(j,i)=a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c。
然后value(x)=f[x]+g(x,i)=f[x]+a*(sum[i]-sum[x])*(sum[i]-sum[x])+b*(sum[i]-sum[x])+c。
如果j<k时，value(j)-value(k)>0可以化成K(j,k)>H(i)的形式（这时K(j,k)>H(i)等价于j比k优），且H(i)是单调递增的，我们就可以用斜率优化了。
当j<k时，对value(j)-value(k)>0变形，得：
2*a*sum[i]*(sum[k]-sum[j])>f[k]-f[j]+b*(sum[j]-sim[k])+a*(sum[k]*sum[k]-sum[j]*sum[j])
sum[i]<(f[k]-f[j]+b*(sum[j]-sim[k])+a*(sum[k]*sum[k]-sum[j]*sum[j])) / (2*a*(sum[k]-sum[j])) /*因为a<0，sum[k]-sum[j]>0，所以反号*/
这时，我们看到了曙光！！
K(j,k)=(f[k]-f[j]+b*(sum[j]-sim[k])+a*(sum[k]*sum[k]-sum[j]*sum[j])) / (2*a*(sum[k]-sum[j]))
H(i)=sum[i]
满足K(j,k)>H(i)，H(i)递增，所以我们可以斜率优化了，恩，就是这样，代码见这里。