概论
斜率优化是一种优化 1D/1D 动态规划的方法。
引例1 [HNOI2008]玩具装箱TOY
动态转移方程 记 $s_i=i+\sum_{j=1}^iC_j$，$f_i$ 表示前 $i$ 个玩具的最小花费，那么有：
其中，$w(j+1,i)=(s_i-s_j-L-1)^2$。
斜率优化 记 $a_i=s_i,b_j=s_j+L+1$，那么有 ：
将只与 $j$ 有关的放在右边，得：
将等式右边看作 $y$，$b_j$ 看作 $x$，那么这条直线的斜率就是 $2a_i$。
我们要让 $f_i$ 最小，不如看作在 $j\in[0,i-1]$ 中的 $(b_j,f_j+b_j^2)$ 的点中选一个点让斜率为 $2a_i$ 的直线经过，让截距最小。如果把这些点在平面直角坐标系中画出来，我们发现，最优决策点是下凸壳上斜率最大且小于 $2a_i$ 的点。我们维护一个下凸壳，它的实际意义是斜率单调递增，这启发我们可以二分找到斜率小于 $i$ 的斜率 $2a_i$ 的编号最大的点。但是进一步的，由于 $a_i$ 单调递增，所以可以用单调队列维护。
$\text{Code}$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> #define REG register #define MAXN 50005 #define LL long long #define D double using namespace std ;inline LL read () REG LL x (0 ) ; REG char c=getchar(); while (!isdigit (c)) c=getchar(); while (isdigit (c)) x=(x*10 )+(c^48 ),c=getchar(); return x; } LL s[MAXN],a[MAXN],b[MAXN],dp[MAXN],L,n; inline D getSlope (int j1,int j2) return (double )(dp[j2]+b[j2]-dp[j1]-b[j1])/(a[j2]-a[j1]);}int head=1 ,tail=0 ,Q[MAXN];int main () n=read(),L=read(); for (REG int i=1 ;i<=n;++i){ int t=read(); a[i]=a[i-1 ]+t+1 ; b[i]=(a[i]+L+1 )*(a[i]+L+1 ); } b[0 ]=(L+1 )*(L+1 ); Q[++tail]=0 ; for (REG int i=1 ;i<=n;++i){ while (head<tail&&getSlope(Q[head],Q[head+1 ])<=(a[i]<<1 )) ++head; dp[i]=dp[Q[head]]+(a[i]-a[Q[head]]-L-1 )*(a[i]-a[Q[head]]-L-1 ); while (head<tail&&getSlope(Q[tail],i)<getSlope(Q[tail-1 ],Q[tail])) --tail; Q[++tail]=i; } printf ("%lld\n" ,dp[n]); }
引例2 [APIO2010]特别行动队
动态转移方程 $f_i=\max_{0\le j<i}\{f_j+w(j+1,i)\}$
$w(j+1,i)=a(s_i-s_j)^2+b(s_i-s_j)+c$
$w(j+1,i)=as_i^2+as_j^2-2as_is_j+bs_i-bs_j+c$
斜率优化 $2as_is_j+f_i-(as_i^2+bs_i)=(f_j+as_j^2-bs_j+c)$
一条斜率为 $2as_i$ 的直线经过了 $(s_j,f_j+as_j^2-bs_j+c)$，我们要最大化截距。
那么就是要候选决策点成为一个上凸壳，也就是斜率单调递减。找到一个斜率最小且大于 $2as_i$ 的点即可，利用单调队列解决该问题。
$\text{Code}$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> #define REG register #define LL long long #define D double #define MAXN 1000005 using namespace std ;inline LL read () REG LL x (0 ) ; REG int s (0 ) ; REG char c=getchar(); while (!isdigit (c)) s=c^45 ?s:1 ,c=getchar(); while (isdigit (c)) x=(x*10 )+(c^48 ),c=getchar(); return s?-x:x; } LL n,a,b,c; LL dp[MAXN],s[MAXN],f[MAXN]; int Q[MAXN],head=1 ,tail;inline D getSlope (int j1,int j2) return (D)(dp[j2]+f[j2]-dp[j1]-f[j1])/(s[j2]-s[j1]);}void Work () n=read(),a=read(),b=read(),c=read(); for (REG int i=1 ;i<=n;++i) s[i]=s[i-1 ]+read(),f[i]=a*s[i]*s[i]-b*s[i]+c; f[0 ]=c,Q[++tail]=0 ; for (REG int i=1 ;i<=n;++i){ while (head<tail&&getSlope(Q[head],Q[head+1 ])>=s[i]*(a<<1 )) ++head; dp[i]=dp[Q[head]]+a*(s[i]-s[Q[head]])*(s[i]-s[Q[head]])+b*(s[i]-s[Q[head]])+c; while (head<tail&&getSlope(Q[tail-1 ],Q[tail])<getSlope(Q[tail],i)) --tail; Q[++tail]=i; } printf ("%lld\n" ,dp[n]); } int main () Work(); }
