土地购买[Usaco2008 Mar]

题目传送门

1597: [Usaco2008 Mar]土地购买

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 5925 Solved: 2243
[Submit][Status][Discuss]

Description

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <

= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价

格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要

付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

Input

* 第1行: 一个数: N

* 第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽

Output

* 第一行: 最小的可行费用.

Sample Input

4
100 1
15 15
20 5
1 100
输入解释:
共有4块土地.

Sample Output

500
FJ分3组买这些土地:
第一组:100x1,
第二组1x100,
第三组20x5 和 15x15 plot.
每组的价格分别为100,100,300, 总共500.

HINT

Source

Gold

　　首先我们看到每组选择的土地可以是不连续的，这给我们造成了不小的麻烦。

　　我们思考一下题意，可以发现若一个矩形的长和宽都不大于另一个矩形的长和宽，那么这个矩形就不用考虑了。

　　怎么删除这些无用矩形呢？

　　我们先按长为第一关键字，宽为第二关键字进行降序排序，然后就可以比较轻松地删去无用矩形。

　　而且我们可以发现最后得到的序列的长单调递减，宽单调递增。也就是说如果选其中两个矩形为一组，序列中位于这两个矩形中间的矩形都是可以免费加入改组的。所以每一组的区间就是连续的。

　　于是我们就可以用f[i]表示购买前i块土地的最小花费。转移方程为f[i] = min{f[j]+l[j+1]*r[i]}.

　　但这样转移复杂度是O（n^2）的，还是不满足数据要求。

　　所以我们考虑斜率优化。状态转移复杂度优化为O（n）. （还没学习斜率优化的同学可以看一下大米饼的博客，强烈推荐。传送门）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define LL long long
 6 #define RI register int
 7 using namespace std;
 8 const int INF = 0x7ffffff ;
 9 const int N = 50000 + 10 ;
10 
11 inline int read() {
12     int k = 0 , f = 1 ; char c = getchar() ;
13     for( ; !isdigit(c) ; c = getchar())
14       if(c == '-') f = -1 ;
15     for( ; isdigit(c) ; c = getchar())
16       k = k*10 + c-'0' ;
17     return k*f ;
18 }
19 struct data {
20     LL l, r ;
21 }gg[N], hh[N] ;
22 int n ; int q[N] ; LL f[N] ;
23 
24 inline double X(int i) { return -hh[i+1].l ; }
25 inline double Y(int i) { return f[i] ; }
26 inline double Rate(int i,int j) { return (Y(j)-Y(i))/(X(j)-X(i)) ; }
27 
28 inline bool cmp1(data s,data t) { return s.l == t.l ? s.r > t.r : s.l > t.l ; }
29 int main() {
30     n = read() ;
31     for(int i=1;i<=n;i++) gg[i].l = read(), gg[i].r = read() ;    
32     sort(gg+1,gg+n+1,cmp1) ; int tt = 0 ;
33     for(int i=1;i<=n;) {
34         hh[++tt] = gg[i] ;  int j=i+1 ;
35         while(gg[j].l <= gg[i].l && gg[j].r <= gg[i].r) j++ ;
36         i = j ;
37     }  n = tt ;
38     int head = 1, tail = 1 ; q[1] = 0 ;
39     for(int i=1;i<=n;i++) {
40         while(head < tail && Rate(q[head],q[head+1]) < hh[i].r) head++ ;
41         int j = q[head] ; f[i] = f[j]+hh[j+1].l*hh[i].r ;
42         while(head < tail && Rate(q[tail-1],q[tail]) > Rate(q[tail],i)) tail-- ;
43         q[++tail] = i ;
44     }
45     printf("%lld",f[n]) ;
46     return 0 ;
47 }