洛谷 P2900 土地征用Land Acquisition 斜率优化

传送~

Description

有$n$块土地,每块土地的长和宽分别为$l_i,w_i$.土地可以单独买也可以一起买.当购买的土地的组合为集合$S(size_S\geq 1)$时, 价格为$S$中最大的长*最大的宽,即$l_{max}\times w_{max}$ .求购买所有土地的最小费用.

$n\leq 5\times 10^4,l_i,w_i\leq 10^6$

Solution

初看到这道题,我是**的,也列不出任何转移方程.但这毕竟是道斜率优化题,于是我们就要有点斜率优化的样子,于是…

操作一

由于费用与一组土地中长和宽的最大值有关,所以我们可以先将一维(如宽)拍好序,那么$w_i$即为$1$至$i$中的$w_{max}$.当$i$与$1$至$(i-1)$的土地组合时,费用的一维就确定了.

尽管一维确定了,但由于可以随意组合,另一维是不确定的,所以我们仍毫无头绪.

结论一

接着由题意显然可以得到第一个结论:当$l_i\leq l_j$且$w_i\leq w_j$时$i$对费用是没有贡献的.所以我们可以把这样的土地删除.

为什么?

当$j$被购买时,设费用为$l_0\times w_0,l_0\geq l_j,w_0\geq w_j$.若将$i$与$j$一同购买,费用是不会增加的.所以我们在购买$j$时自动购买$i$,就可以把$i$删掉了.

但这跟斜率优化,甚至跟DP有什么关系呢?

操作二

利用我们的排序操作和第一个结论,我们可以得到一个宽单调递增,长单调递减的土地的序列.宽单调递增很容易理解,因为这是排序的关键字.但为什么长单调递减?

因为排序后$\forall 1\leq j<i,w_j<w_i$,所以只要当$l_j\leq l_i$时,$j$就可以被删掉了.所以我们用单调栈维护,使栈中$l$递减.从前往后扫,扫到$i$时,把小于$l_i$的都弹掉.

结论二

这时我们就可以得到第二个结论了:每一个购买组合都必须是一段连续的土地序列.

为什么?

我们设$j<i$,若$i$与$j$一起买,由上面的一系列操作,我们可以知道价格为$w_i\times l_j$.对于$\forall j<k<i$,由于宽单调递增,长单调递减,故$w_k<w_i,l_k<l_j$,所以$k$对于费用是没有影响的,所以我们不妨把这些$k$与$i$和$j$一起买,即购买区间$[j,i]$.

终于,我们可以开始推式子了…

DP

设$f_i$为前$i$块土地都购买了的最小费用.由上面一波操作,我们可以得到如下的转移方程

在区间$(j,i]$中,$w_{max}=w_i,l_{max}=l_{j+1}$,故转移费用为$w_i\times l_{j+1}$.

这已经不是斜率优化入门题了,所以我们直接上套路.

我们设$j>k$, 若从$j$转移比$k$更优,则必须满足

由于$j>k$,$l$单调递减,故$l_{k+1}-l_{j+1}>0$,可以直接除过去.

很容易发现这是一次函数的点斜式.我们设$slope(j,k)$为上面的左式,即斜率.则当$j>k$且$slope(j,k)<w_i$时,$j$比$k$优.由于$w_i$单调递增,我们可以用单调队列维护斜率,使$slope(i+1, i)$单调递增,且队首最优.

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4;
typedef long long ll;
int n, cnt, l, r, q[maxn+10], tag[maxn+10];
ll f[maxn+10];
struct land {
int wid, len;
} a[maxn+10], b[maxn+10];
int cmp(land x, land y) {
return x.wid != y.wid ? x.wid < y.wid : x.len < y.len;
}
double slope(int j, int k) {
return 1.0*(f[j]-f[k])/(b[k+1].len-b[j+1].len);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &a[i].wid, &a[i].len);
sort(a+1, a+1+n, cmp); //按w排序
for (int i = 1; i <= n; ++i) {
while (cnt && a[i].len >= b[cnt].len) --cnt;
b[++cnt] = a[i];
} //单调栈
for (int i = 1; i <= cnt; ++i) {
while (l < r && slope(q[l+1], q[l]) < b[i].wid) ++l; //此时q[l]比q[l+1]更劣,由于x[i]递增,故之后一直更劣,弹出
f[i] = f[q[l]]+1ll*b[i].wid*b[q[l]+1].len; //记得要1ll
while (l < r && slope(q[r], q[r-1]) > slope(i, q[r])) --r; //保持队列中斜率单调递增
q[++r] = i;
}
printf("%lld\n", f[cnt]); //一定记得开longlong
return 0;
}

THANK YOU FOR READING THIS!