首页 > 代码库 > BZOJ1597: [Usaco2008 Mar]土地购买

BZOJ1597: [Usaco2008 Mar]土地购买

2024-07-17 03:59:53   227人阅读

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了
代码：
 1 const maxn=50000+100; 2 type node=record 3      x,y:int64; 4      end; 5 var a,b:array[0..maxn] of node; 6     q,sta:array[0..maxn] of longint; 7     i,n,top,l,r:longint; 8     f:array[0..maxn] of int64; 9 function cmp(a,b:node):boolean;10  begin11  if a.x=b.x then exit(a.y<b.y) else exit(a.x<b.x);12  end;13 procedure sort(l,r:longint);14  var i,j:longint;x,y:node;15  begin16  i:=l;j:=r;x:=a[(i+j)>>1];17  repeat18   while cmp(a[i],x) do inc(i);19   while cmp(x,a[j]) do dec(j);20   if i<=j then21    begin22    y:=a[i];a[i]:=a[j];a[j]:=y;23    inc(i);dec(j);24    end;25  until i>j;26  if i<r then sort(i,r);27  if j>l then sort(l,j);28  end;29 procedure init;30  begin31  readln(n);32  for i:=1 to n do readln(a[i].x,a[i].y);33  sort(1,n);34  for i:=1 to n do35   begin36   while (top>0) and (a[i].y>=a[sta[top]].y) do dec(top);37   inc(top);sta[top]:=i;38   end;39  for i:=1 to top do b[i]:=a[sta[i]];n:=top;40  end;41 function k(i,j:longint):double;42  begin43  k:=(f[i]-f[j])/(b[j+1].y-b[i+1].y);44  end;45 function w(i,j:longint):int64;46  begin47  w:=f[j]+b[j+1].y*b[i].x48  end;49 procedure main;50  begin51  l:=0;r:=0;52  for i:=1 to n do53   begin54   while (l<r) and (k(q[l+1],q[l])<b[i].x) do inc(l);55   f[i]:=w(i,q[l]);56   while (l<r) and (k(i,q[r])<k(q[r],q[r-1])) do dec(r);57   inc(r);q[r]:=i;58   end;59  writeln(f[n]);60  end;61 begin62   assign(input,‘input.txt‘);assign(output,‘output.txt‘);63   reset(input);rewrite(output);64   init;65   main;66   close(input);close(output);67 end.
View Code

 


联系
我们