bzoj1597 [Usaco2008 Mar]土地购买

【bzoj1597】[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.

这个还是不难的，这题目，可以维护成下三角类型，什么之类的，然后合并成新的序列，这样就可以得出斜率方程了。

还是转移hzw的。

按照x，y递增排序，然后把可以和其它打包一起买的去掉

然后使得剩下一些y递减x递增的矩形

显然f[i]=min(f[j]+y[j+1]x[i])

然后再搞个斜率优化

方程是(f[j]-f[k])/(y[k+1]-y[j+1])<x[i]

然后维护一个下凸包

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 const int NN=1e6+7;
10 
11 int n,l,r;
12 ll x[NN],p[NN],c[NN],q[NN];
13 ll f[NN],sum[NN],b[NN];
14 double get_left(int j,int k)
15 {
16     return (f[j]-f[k]+b[j]-b[k])*1.0/(double)(sum[j]-sum[k]);
17 }
18 int main()
19 {
20     //freopen("1.in","r",stdin);
21     //freopen("fzy.out","w",stdout);
22     scanf("%d",&n);
23     for (int i=1;i<=n;i++)
24     {
25         scanf("%d%d%d",&x[i],&p[i],&c[i]);
26         sum[i]=sum[i-1]+p[i];
27         b[i]=b[i-1]+p[i]*x[i];    
28     }
29     l=0;
30     q[r++]=0;
31     for (int i=1;i<=n;i++)
32     {
33         while(l+1<r&&(get_left(q[l+1],q[l])<=x[i])) l++;
34         int best=q[l];
35         f[i]=f[best]+(sum[i]-sum[best])*x[i]-(b[i]-b[best])+c[i];
36         while(r-2>=l&&get_left(q[r-1],q[r-2])>get_left(i,q[r-1])) r--;
37         q[r++]=i;    
38     }
39     printf("%lld",f[n]);
40 }