何时使用斜率优化？

当dpdp的状态转移方程可以转换成形如fi=max/min(yj+k∗xj)(j<i)f_i=max/min(y_j+k*x_j)_{(j<i)}的形式时，可以构造凸包来维护对于每一个ii最优的决策点jj

凸包的维护

维护一个双端队列，

比如需维护上凸包时，新加进的点如果和队尾点形成直线的斜率大于等于队尾两个点的斜率，就需要弹出队尾，重复这一过程直到小于或者队内只有一点，最后再加入新点。

下凸包也一样。

值得注意的是，由于除法有精度损失，所以比较时可以采用移项转乘法来精确比较。

如何判断需要维护上凸包还是下凸包？

推式子，

比如如果状态转移方程是fi=max(yj+k∗xj)(j<i)f_i=max(y_j+k*x_j)_{(j<i)}，
那对于xa<xb<xcx_a<x_b<x_c三个决策点，因为bb有作为某些询问最优转移点的时刻，所以对于这些时刻的kk有:

ya+k∗xa<yb+k∗xby_a+k*x_a<y_b+k*x_b

yc+k∗xc<yb+k∗xby_c+k*x_c<y_b+k*x_b

移项得：

−k<yb−yaxb−xa-k<\cfrac{y_b-y_a}{x_b-x_a}

−k>yc−ybxc−xb-k>\cfrac{y_c-y_b}{x_c-x_b}

这也就说明我们需要维护的是一个上凸包，因为只有在−k-k比abab线的斜率小、比bcbc线的斜率大时，取bb为转移点才是最优的；若bcbc线的斜率大于等于abab线的斜率，则使bb点为最优决策点的kk的取值范围为空集，那么bb也就不是一个决策点。

minmin的时候也是同理。

如何回复询问？

询问应当是单调的，而且与凸包的单调性相匹配，比如上凸包对应的−k-k的单调性应为单调下降，下凸包则相反，查询即从队头开始，比如上凸包，若队头的线对应斜率大于−k-k，则应弹出队头，直到小于或队中只有一点，此时用队头的点作为最优决策点计答案即可。反之亦然。

ps:斜率不单调怎么办？其实可以，维护组成凸包的点时用数组模拟双端队列，既然里面的斜率是单调的，那就可以二分找到第一个计答案比后一个点优的点，它必然是最优转移点

几个例题

平面中有nn个点(xi,yi)(x_i,y_i)，有mm条直线，斜率kk已经确定，需要在给定的nn个点中，选出一个点(xi,yi)(x_i,y_i)，使得kx+ykx+y最大。

单纯维护斜率和查询，直接上代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,m,ans[100050];
struct node{
	ll x,y;
	bool operator <(const node &a)const{
		return x<a.x||(x==a.x&&y>a.y);
	}
}p[100050],pre1,pre2;
struct query{
	ll pos,k;
	bool operator <(const query &a)const{
		return k>a.k;
	}
}q[100050];
deque<node> st;
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&p[i].x,&p[i].y);
	}
	sort(p+1,p+1+n);
	for(int i=1;i<=m;i++){
		scanf("%lld",&q[i].k);
		q[i].pos=i;
	}
	sort(q+1,q+1+m);
	for(int i=1;i<=n;i++){
		if(st.size()<2){
			if(st.size()>0){
				if(p[i].x==st.front().x){
					if(p[i].y>st.front().y)st.pop_front();
					else if(p[i].y<=st.front().y)continue;
				}
			}
			st.push_back(p[i]);
			continue;
		}
		ll pd=1;
		while(st.size()>=2){
			pre1=st.back();
			st.pop_back();
			pre2=st.back();
			st.pop_back();
			if((double)(p[i].y-pre1.y)*(pre1.x-pre2.x)<(double)(pre1.y-pre2.y)*(p[i].x-pre1.x)){
				st.push_back(pre2);
				st.push_back(pre1);
				st.push_back(p[i]);
				break;
			}
			else{
				st.push_back(pre2);
			}
		}
		st.push_back(p[i]);
	}
	ll cnt=m;
	while(cnt>0&&st.size()>1){
		pre1=st.front();
		st.pop_front();
		pre2=st.front();
		if(-q[cnt].k*(pre2.x-pre1.x)>(pre2.y-pre1.y))
		ans[q[cnt].pos]=pre1.x*q[cnt].k+pre1.y,st.push_front(pre1),cnt--;
	}
	while(cnt>0){
		pre1=st.front();
		ans[q[cnt].pos]=pre1.x*q[cnt].k+pre1.y;
		cnt--;
	}
	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}

Kano准备扩大他的农场，眼下必须购买N≤5e4N\le5e4块长方形土地。如果Kano买一块土地，价格就是土地的面积。他也可以选择并购多块土地，并购的价格为这些土地中最大的长乘以最大的宽，比如Kano购买3∗53*5和5∗35*3的土地，只需要支付5∗5=255*5=25元，比分开买合算。请你帮他计算购买所有土地的最小费用。

首先一个显然的性质是如果对于一块地有另一块地长宽均大于等于它，那它可以直接与那一块合并而不付出任何代价；
其次，我们对清除完合并无需付出代价的地块后，按长单增排序，宽也就会按从大到小排好，甚至是单调减而非单调不上升，根据前一个性质即可得到；
排序后我们可以得到一个dpdp状态转移方程：fi=min(fj+wj+1∗li)j<if_i=min(f_j+w_{j+1}*l_i)_{j<i}其中ww为宽，ll为长，往上面套套路即可。
值得注意的是，这个凸包是以xx从大到小造的，所以维护的时候还需思考它的判断式子该怎么写。

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
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,cnt,l=0,r=0,f[100000];
struct node{
    ll x,y;
    bool operator <(const node &a)const{
        return x<a.x||(x==a.x&&y<a.y);
    }
}c[100000],b[100000];
struct point{
    ll x,y;
}p[100000],tmp;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&c[i].x,&c[i].y);
    }
    sort(c+1,c+1+n);
    for(int i=1;i<=n;i++){
        while(cnt>0&&b[cnt].x<=c[i].x&&b[cnt].y<=c[i].y)cnt--;
        b[++cnt]=c[i];
    }
    tmp.x=b[1].y;
    tmp.y=0;
    p[++r]=tmp;
    for(int i=1;i<=cnt;i++){
        while(r-l>1&&-b[i].x<=(p[l+2].y-p[l+1].y)/(p[l+2].x-p[l+1].x)){
            l++;
        }
        f[i]=p[l+1].x*b[i].x+p[l+1].y;
        tmp.x=b[i+1].y;
        tmp.y=f[i];
        while(r-l>1&&(tmp.y-p[r].y)*(p[r].x-p[r-1].x)>=(p[r].y-p[r-1].y)*(tmp.x-p[r].x)){
            r--;
        }
        p[++r]=tmp;
    }
    printf("%lld",f[cnt]);
    return 0;
}

玩具装箱
这题不难得到状态转移方程fi=min(fj+(i−j−1−L+∑k=j+1ick)2)(j<i)f_i=min(f_j+(i-j-1-L+\sum^{i}_{k=j+1}c_k)^2)_{(j<i)},
但这个式子比较抽象不好看，可以转换一下，把区间和变成前缀和相减的形式，再把前面加与减的ii和jj正好按同符号放进去，可得fi=min(fj+(sumi−sumj−L−1)2)(j<i)f_i=min(f_j+(sum_i-sum_j-L-1)^2)_{(j<i)}，
再把与jj有关和无关的拆分整理可得fi−(sumi−L−1)2=min(fj+sumj2−2∗(sumi−L−1)∗sumj)(j<i)f_i-(sum_i-L-1)^2=min(f_j+sum_j^2-2*(sum_i-L-1)*sum_j)_{(j<i)},
这时候再套板子就行了，和前一个题一样，这个也是倒着造凸包。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,L,f[100050],sum[100050],l=0,r=0;
struct node{
    ll x,y;
}p[100050],tmp;
int main(){
    scanf("%lld%lld",&n,&L);
    L++;
    for(int i=1;i<=n;i++){
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-1]+1;
    }
    tmp.x=0;
    tmp.y=0;
    p[++r]=tmp;
    for(int i=1;i<=n;i++){
        ll k=sum[i]-L;
        while(r-l>1&&-k<=(p[l+2].y-p[l+1].y)/(p[l+2].x-p[l+1].x)){
            l++;
        }
        f[i]=k*k+p[l+1].y+p[l+1].x*k;
        tmp.x=-2*sum[i];
        tmp.y=f[i]+sum[i]*sum[i];
        while(r-l>1&&(tmp.y-p[r].y)*(p[r].x-p[r-1].x)>=(p[r].y-p[r-1].y)*(tmp.x-p[r].x)){
            r--;
        }
        p[++r]=tmp;
    }
    printf("%lld",f[n]);
    return 0;
}

第一次修订：增加了关于查询非单调的处理方法。