【DP】斜率优化学习笔记
GIFBMP
·
·
个人记录
前言
斜率优化：看起来很难，学起来异常水。
十分套路，但也十分灵活的一种优化。
一、套路
斜率优化一般用来解决一下这种 DP 式：
f_i=\min\{f_j+a_ib_j+c_i+d_j\}
或
f_i=\max\{f_j+a_ib_j+c_i+d_j\}
其中 a_ib_j 这一项既有 i 又有 j，因此不能单调队列优化。
那么我们设 j1,j2 满足 j1<j2 且 j2 优于 j1，移项后可以得到：
\dfrac{X(j2)-X(j1)}{Y(j2)-Y(j1)}<k
或
\dfrac{X(j2)-X(j1)}{Y(j2)-Y(j1)}>k
我们先来讨论情况 1。
如果存在 2 个数 j1，j2 满足情况 1 且 j1<j2 的话，那么很显然 j2 优于 j1，也就是说，如果 (X(j1),Y(j1)) 和 (X(j2),Y(j2)) 构成的直线的斜率 <k，那么 j2 优于 j1，否则 j1 优于 j2。
如图，平面上有点 A,B,C，其中 k1 为 AB 所在直线的斜率，k2 为 BC 所在直线的斜率，满足 k2<k1。
根据上述结论，得：
当 k<k2<k1 时，明显 A 优于 B 优于 C。
当 k2<k<k1 时，明显 A,C 均比 B 优。
当 k2<k1<k 时，明显 C 优于 B 优于 A。
我们发现，无论如何，B 均不是最优，于是将 B 丢出去，那么就得到了这样一个图像：
我们发现这就是一个维护下凸壳的过程，于是用单调队列维护下凸壳即可。
那么对于第一种情况，维护下凸壳，第二种情况同理，维护上凸壳即可。
PS:只有当斜率 k 具有单调性的时候能这么做，否则需要在凸壳上二分。
二、例题
[ZJOI2007]仓库建设
设 f_i 表示到 i 的最小代价，显然可以得出：
f_i=\min\{f_j+\sum_{k=j+1}^{i}p_kx_i-\sum_{k=j+1}^ip_kx_k+c_i\}
设 sump_i=\sum_{j=1}^ip_j，sum_i=\sum_{j=1}^ip_jx_j，化简得：
f_i=\min\{f_j+sump_ix_i-sump_jx_i-sum_i+sum_j+c_i\}
我们按照套路，设 j1,j2 满足 j1<j2 且 j2 优于 j1，得：
f_{j2}+sump_ix_i-sump_{j2}x_i-sum_i+sum_{j2}+c_i<f_{j1}+sump_ix_i-sump_{j1}x_i-sum_i+sum_{j1}+c_i
f_{j2}-sump_{j2}x_i+sum_{j2}<f_{j1}-sump_{j1}x_i+sum_{j1}
(f_{j2}+sum_{j2})-(f_{j1}+sum_{j1})<(sump_{j2}-sump_{j1})x_i
\dfrac{(f_{j2}+sum_{j2})-(f_{j1}+sum_{j1})}{sump_{j2}-sump_{j1}}<x_i
设 X(i)=f_i+sum_i，Y(i)=sump_i，那么就转化成了上面的情况 1，于是维护下凸壳即可。
Code:
```cpp
#include <cstdio>
#define int long long
using namespace std ;
const int MAXN = 1e6 + 10 ;
int n , L , f[MAXN] , sum[MAXN] , sump[MAXN] , c[MAXN] , x[MAXN] , p[MAXN] ;
int q[MAXN] , head = 1 , tail = 1 ;
double slope (int j1 , int j2) {
return (f[j2] + sum[j2] - f[j1] - sum[j1]) * 1.0 / (sump[j2] - sump[j1]) ;
}
signed main () {
scanf ("%lld" , &n) ;
for (int i = 1 ; i <= n ; i++) {
scanf ("%lld %lld %lld" , &x[i] , &p[i] , &c[i]) ;
sump[i] = sump[i - 1] + p[i] ;
sum[i] = sum[i - 1] + p[i] * x[i] ;
}
for (int i = 1 ; i <= n ; i++) {
while (head < tail && slope (q[head] , q[head + 1]) < x[i]) head++ ;
int j = q[head] ;
f[i] = f[j] + sump[i] * x[i] - sump[j] * x[i] - sum[i] + sum[j] + c[i] ;
while (head < tail && slope (q[tail] , i) <= slope (q[tail - 1] , q[tail])) tail-- ;
q[++tail] = i ;
}
printf ("%lld" , f[n]) ;
return 0 ;
}
```
#### [[APIO2010]特别行动队](https://www.luogu.com.cn/problem/P3628)
还是按照套路，设 $f_i$ 表示到 $i$ 时的答案，设 $sum_i=\sum_{j=1}^ix_j$，易得：
$$f_i=\max\{f_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)+c\}$$
我们还是套路，设 $j1,j2$ 满足 $j1<j2$ 且 $j2$ 优于 $j1$，得：
$$f_{j2}-2asum_isum_{j2}+asum_{j2}^2-bsum_{j2}>f_{j1}-2asum_isum_{j1}+asum_{j1}^2-bsum_{j1}$$
$$(f_{j2}+asum_{j2}^2-bsum_{j2})-(f_{j1}+asum_{j1}^2-bsum_{j1})>(sum_{j2}-sum_{j1})2asum_i$$
$$\dfrac{(f_{j2}+asum_{j2}^2-bsum_{j2})-(f_{j1}+asum_{j1}^2-bsum_{j1})}{sum_{j2}-sum_{j1}}>2asum_i$$
我们设 $X(i)=f_i+asum_i^2-bsum_i$，$Y(i)=sum_i$，那么就转化成了上面的情况 $2$，维护上凸壳即可。
Code:
```cpp
#include <cstdio>
#define int long long
using namespace std ;
const int MAXN = 1e6 + 10 ;
int n , a , b , c , f[MAXN] , sum[MAXN] ;
int q[MAXN] , head = 1 , tail = 1 ;
double slope (int j1 , int j2) {
return ((f[j2] + a * sum[j2] * sum[j2] - b * sum[j2]) - (f[j1] + a * sum[j1] * sum[j1] - b * sum[j1])) * 1.0 / (sum[j2] - sum[j1]) ;
}
signed main () {
scanf ("%lld %lld %lld %lld" , &n , &a , &b , &c) ;
for (int i = 1 ; i <= n ; i++) {
scanf ("%lld" , &sum[i]) ;
sum[i] += sum[i - 1] ;
}
for (int i = 1 ; i <= n ; i++) {
while (head < tail && slope (q[head] , q[head + 1]) > 2 * a * sum[i]) head++ ;
int j = q[head] ;
f[i] = f[j] + a * (sum[i] - sum[j]) * (sum[i] - sum[j]) + b * (sum[i] - sum[j]) + c ;
while (head < tail && slope (q[tail - 1] , q[tail]) <= slope (q[tail] , i)) tail-- ;
q[++tail] = i ;
}
printf ("%lld" , f[n]) ;
return 0 ;
}
```