BZOJ1597: [Usaco2008 Mar]土地购买

1597: [Usaco2008 Mar]土地购买

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1448  Solved: 504
[Submit][Status]

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

HINT

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

Source

Gold

题解：

巧妙的斜率优化。

考虑到把某一个元素按递增排序，另一个元素（有用的）一定是单调减的！

所谓有用就是没有一块地既比它高、又比它宽，否则可以被这块覆盖掉

然后就可以写出状态转移方程了，然后就是喜闻乐见的斜率优化的DP了

代码：

const maxn=50000+100;
type node=record
     x,y:int64;
     end;
var a,b:array[0..maxn] of node;
    q,sta:array[0..maxn] of longint;
    i,n,top,l,r:longint;
    f:array[0..maxn] of int64;
function cmp(a,b:node):boolean;
 begin
 if a.x=b.x then exit(a.y<b.y) else exit(a.x<b.x);
 end;
procedure sort(l,r:longint);
 var i,j:longint;x,y:node;
 begin
 i:=l;j:=r;x:=a[(i+j)>>1];
 repeat
  while cmp(a[i],x) do inc(i);
  while cmp(x,a[j]) do dec(j);
  if i<=j then
   begin
   y:=a[i];a[i]:=a[j];a[j]:=y;
   inc(i);dec(j);
   end;
 until i>j;
 if i<r then sort(i,r);
 if j>l then sort(l,j);
 end;
procedure init;
 begin
 readln(n);
 for i:=1 to n do readln(a[i].x,a[i].y);
 sort(1,n);
 for i:=1 to n do
  begin
  while (top>0) and (a[i].y>=a[sta[top]].y) do dec(top);
  inc(top);sta[top]:=i;
  end;
 for i:=1 to top do b[i]:=a[sta[i]];n:=top;
 end;
function k(i,j:longint):double;
 begin
 k:=(f[i]-f[j])/(b[j+1].y-b[i+1].y);
 end;
function w(i,j:longint):int64;
 begin
 w:=f[j]+b[j+1].y*b[i].x
 end;
procedure main;
 begin
 l:=0;r:=0;
 for i:=1 to n do
  begin
  while (l<r) and (k(q[l+1],q[l])<b[i].x) do inc(l);
  f[i]:=w(i,q[l]);
  while (l<r) and (k(i,q[r])<k(q[r],q[r-1])) do dec(r);
  inc(r);q[r]:=i;
  end;
 writeln(f[n]);
 end;
begin
  assign(input,'input.txt');assign(output,'output.txt');
  reset(input);rewrite(output);
  init;
  main;
  close(input);close(output);
end.