BZOJ 1597: [Usaco2008 Mar]土地购买

正文索引 [隐藏]

Description

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3×5的地和一块5×3的地,则他需要付5×5=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组买这些土地: 第一组:100×1, 第二组1×100, 第三组20×5 和 15×15 plot. 每组的价格分别为100,100,300, 总共500.

Source

Gold

题解

找手感找手感!来做DP题!
斜率优化,之前感觉还是很模糊就这么过来了,所以现在巩固一下子。
我们先去掉某些x,y都小于别的土地的土地,进行优化。
然后把x降序,那么y就是升序了。
很容易得到方程 -> f[i]=min{f[j]+x[j+1]y[i]}
我们设两个转移p,q 要转移的当前项为i 且p比q优,很容易推出以下:
f[p]+x[p+1]
y[i]<f[q]+x[q+1]*y[i]
(f[p]-f[q])/(x[q+1]-x[p+1])<y[i]
那么左边就是一个无关当前转移项,此系数小于y[i]即表示p比q优!
那么我们建立一个单调队列,转移前排除队首不那么优的项!
转移后再把它加入队列!那么如何加入队列呢?我们这么考虑。
我们设无关项为g(p,q)=(f[p]-f[q])/(x[q+1]-x[p+1]) 当前转移项为k,有上推得当g(p,q)<y[k]时,p比q优。
现在我们要把i加入队列,此时队尾为q,队尾倒数第二个为p。
若g(q,p)>g(i,q) ,假设有一个转移项k,那么此时可能出现的情况有3种。

  1. y[k]>g(p,q)>g(i,q) 这样p比q优,i比q优!所以q肯定不会取!
  2. g(p,q)>y[k]>g(i,q) 这样i比q优,而q比p优。这样p,q都不取,但是因为我们依次对队尾进行这样的处理,所以此轮我们只需要去掉p,而q必然在下一轮被去掉。
  3. g(p,q)>g(i,q)>y[k] 那么q比p优,q比i优。结束操作!这样保证单调队列的单调性!

代码