可以说，dp是一个庞大的世界，这个从我刚接触dp的时候，我的老师就是这么告诫我的。事实也正是如此，dp模型变化多端，各种优化也是层出不穷。
斜率优化就是dp的一种优化，它基于数形结合的原理，把dp问题利用图像中的斜率进行加速，配合使用单调队列，可以把时间复杂度从O（N^2）降到O（N）。这个可是非常厉害的，要知道我之前真的很少接触编程中的数形结合(之前多校赛有两道数形结合，然后被虐得一逼Orz……)
首先还是惯例，给出这个的官方的论文，周源《浅谈数形结合思想在信息学竞赛中的应用》 Orz……
还是从最简单的例题讲起吧，POJ 2018 。大致题意就是，给出一个长度为N的序列，要求在这个序列里面找一个长度至少为M的连续子序列，使得这个子序列的平均数最大。即区间和除以区间长。数据范围是1<M<N<100,000。
最显然的做法就是枚举满足要求的区间段，然后求一个平均数最大的即可。但是显然O(N^2)的做法会超时。我们于是对所求的东西进行一些数学上的变形和赋予一定的意义。设前缀和数组为sum，sum[i]表示序列中前i个数字的和。那么我们要求的就是max（（sum[i]-sum[j]）/（i-j）），如果我们把（i，sum[i]）和（j，sum[j]）看作两个点的话，那么问题就转化成了任取两个点，使得这两个点的斜率最大。就这样，纯代数的问题就有了几何的解释。
那么，我们又如何找这个最大的斜率呢？我们发现，如果k<j<i，而且K(k，j)>K（j，i），那么显然j点是没有意义的，因为对于任意x>i，K（x，j）<K（x，i）或者K（x，j）<K（x，k），这个自己画个图就很容易理解。即任何一个向上凸出的点对于最后结果都是没有贡献的，那么我们显然在枚举的时候就可以不去枚举它。为了做到这样，我们只需要维护一个单调下凸的折线，如图所示，然后对于一个固定的点x，与之相关的最大斜率显然就是过该点与下凸折线的切线的斜率。在求切线的时候同理也可以使用上下凸去判断。如果x与q[tail]和q[tail-1]构成上凸，那么显然斜率可以更大，当构成第一个下凸后，其斜率一定最大。这个也是画一个图就一目了然了。
具体实现的话，相信看了我刚刚的表述基本上能够猜到，要用到单调队列来实现，用单调队列来维护这样一个单调下凸的折线段，然后再选决策的时候对应找到切线即可，均摊的时间复杂都为O(N)，具体代码如下：
#include<iostream> #include<cstdio> using namespace std; int s[100010],q[100010]; int n,m,t,h; double ans=-100000; double max(double x,double y) { return x>y?x:y; } double K(int x,int y) { return double(s[y]-s[x])/double(y-x); //这样还是有点风险的，可能斜率不存在 } bool maintain(int k,int i,int j) { return K(i,k)>K(k,j); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); s[i]=s[i-1]+x; } for(int i=0;i<=n-m;i++) { while (t>h && maintain(q[t],q[t-1],i)) t--; q[++t]=i; int j; for(j=t;j>h && maintain(q[j],q[j-1],i+m);j--); h=j; ans=max(ans,K(q[j],i+m)); } printf("%d\n",int(ans*1000)); return 0; }还没完呢，这个只是一个例题，模型实在是太明显，接下来我来说一道没那明显的题目。 HDU 3507 ，题目大致意思是说一个打印，打印一行数字的代价是该行数字的平方和再加上一个常数M。你可以自由选择换行，然后问让打印机打出一堆数字所需要的最小代价是多少，数字的个数不超过500，000。
可以说数据范围大得吓人啊~很容易可以想到转移方程dp[i]=min(d[j]+M+(sum[i]-sum[j])^2)，然而这时O(N^2)的，想都不用想会超时。那么，我们还是一样，对这个式子做一些看似没有用的变换。如果说决策j比决策k更优（j>k），那么必有d[j]+M+(sum[i]-sum[j])^2 < d[k]+M+(sum[i]-sum[k])^2 。我们对这个不等式进行变形，最后可以化简成这样(dp[j]+sum[j]^2-dp[k]-sum[k]^2) / (2*sum[j] - 2*sum[k]) < sum[i]。同样的，把(2*sum[j] , dp[j]+sum[j]^2)和(2*sum[k] , dp[k]+sum[k]^2)看作两个点，可以发现，当决策j比决策k更优时，两点之间的斜率小于sum[i]。与刚刚的例题同理，那么我们就可以利用这一点，对这样的一种斜率表示用单调队列维护，如此我们每次就可以直接选取最优的决策。具体代码（一定要注意什么时候应该加‘=’）：
#include<iostream> #include<cstdio> using namespace std; long long s[500010],q[500010],dp[500010]; int h,t,n,m; long long getdp(int x,int y) { return dp[y]+(s[x]-s[y])*(s[x]-s[y]); } long long f(int x) { return dp[x]+s[x]*s[x]; } bool maintain(int k,int i,int j) { return (f(k)-f(i))*(s[j]-s[k])>=(f(j)-f(k))*(s[k]-s[i]); //这里的'='可不能省啊，当时因为这个调了挺久的 } bool judge(int k,int j,int i) { return (f(j)-f(k))<2*s[i]*(s[j]-s[k]); //没有直接写成斜率，因为可能出现斜率不存在的情况 } int main() { while (~scanf("%d%d",&n,&m)) { h=t=0; q[t]=0; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); s[i]=s[i-1]+x; dp[i]=0; } for(int i=1;i<=n;i++) { while (h+1<=t && judge(q[h],q[h+1],i)) h++; dp[i]=getdp(i,q[h])+m; while (h+1<=t && maintain(q[t],q[t-1],i)) t--; q[++t]=i; } printf("%I64d\n",dp[n]); } return 0; }通过这样一个转化的思想，我们瞬间就可以把代数问题几何化，利用斜率的这个凸性优化再加上单调队列的维护可以使得dp快很多。通过观察，或许你能够发现斜率优化dp好像可以总结出一套类似模板的东西。是的，唯一不同的只是斜率的表示不同，我们可以分别写分子分母的两个函数来表示斜率，这样就可以相应的提炼出一个大致的模板。但是呢，目前为止接触的这类题不多，不敢随便就给出来，下次多写写斜率dp验证之后再贴出来吧。
