0%

Project2900_[USACO08MAR]土地征用Land_Acquisition项目报告

摘要:斜率优化入门

P2900 [USACO08MAR]土地征用Land Acquisition

题面

题目分析

首先有些地是可以直接被筛掉的,也就是宽度和高度都比别人小的地,可以直接打包买,所以首先按照高度做第一关键字排序,再用双指针筛出需要的地.

所以,得到一个高度递减,宽度递增的矩形序列.考虑怎样制定它们的购买方案会最优.显然要选择序列中的一段连续区间,这样化去的钱就只有最左边矩形的高乘上最右边矩形的宽,中间的就可以白嫖了.

于是得到一个$O(n^2)$的方程(宽度w,高度l):

$f_{i} = min\{ f_{j-1}+w_{i}*l_{j} \} (1 \leq j \leq i)$

然后看这个方程有点意思,把决策视为点,可以考虑线性规划.

令$f_{j-1}$为$y$,$l_j$为$-x$,$w_i$为斜率,$f_i$作为目标函数$z$.

得到:

$z = -xw_i +y$

即可化成如下形式:

$y = xw_i + z$

$z$作为截距,我们需要将其最小化.

用单调队列维护一个决策集组成的下凸壳就可以了,最优解一定在这条斜率为$w_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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cmath"
#include "cctype"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define slope(i,j) (f[j-1]-f[i-1])/(l[i]-l[j])
const lxl maxn=100010;
lxl n,l_,r;
lxl h[maxn],l[maxn],q[maxn];
double k[maxn],f[maxn];
struct _Node
{
lxl w,l;
bool operator <(const _Node &another)const
{return l==another.l?w>another.w:l>another.l;}
}c[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
int main(void)
{
// freopen("P2900_2.in","r",stdin);
n=read();
for(R int i(1);i<=n;++i)c[i].w=read(),c[i].l=read();
std::sort(c+1,c+1+n);
lxl now=1;
for(R int i(1);i<=n;++i)if(c[now].w<c[i].w)c[++now]=c[i];
for(R int i(1);i<=now;++i)h[i]=c[i].w,l[i]=c[i].l;
l_=1;
for(R int i(1);i<=now;++i)
{
// debug(h[i]);
while(l_<r&&k[r-1]>=slope(q[r],i))--r;
k[r]=slope(q[r],i),q[++r]=i;
while(l_<r&&k[l_]<=h[i])++l_;
f[i]=(double)(l[q[l_]]*h[i])+f[q[l_]-1];
// printf("%lf\n",f[i]);
}
printf("%lld\n",(lxl)f[now]);
return 0;
}