Mayflyyh
Mayflyyh
MayFlyyh's Blog
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
第一组:100×1,
第二组1×100,
第三组20×5 15×15 plot.
每组的价格分别为100,100,300, 总共500.

是的,人傻就要多DP,打算持续DP很长时间了

第一次做斜率优化DP

发现变形过的式子可能就失去了其原本的物理意义了

对于i来说
如果f[q]+y[q+1]_x[i] q比k优

f[q]-f[k]

只要 (f[q]-f[k]) / (y[k+1]-y[q+1] < x[i] ① 那么 q比k优

所以换成单调队列,将设q=q[head+1]

](队首下一个) ,k=q[head] (队首)
则队首下一个比队首好,就再见此时的队首

另外说明一下 因为x[i]是递增的 所以如果① 满足小于x[i]
必然是满足小于x[i+1]的,所以对后序不会有影响的

再见队尾:

如果tail 比 tail-1 优 说明tail-1有存在的价值,tail也有存在的价值
因为如果x[i]不满足①式,随着x[i]增大可能就满足了

但如果i比tail优,那tail便没有意义了

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
int n;
struct sq{
    ll x,y; 
    bool operator < (const sq m) const{
        if(x==m.x)  return y>m.y;
        return x<m.x;
    }
}a[50050];
ll x[50050],y[50050];
int cnt;
int q[50050],head=1,tail=0;
ll F[50050];
inline double MZ(int q,int k){ //如果结果小于x[i]了话 那么q好 
    return (double)(1.0*(F[q]-F[k]))/(1.0*(y[k+1]-y[q+1]));
}
int main (){
    scanf("%d",&n); 
    for(int i=1;i<=n;++i){
        scanf("%lld %lld",&a[i].x,&a[i].y);
    }
    std::sort(a+1,a+1+n);


    for(int i=1;i<=n;++i){
        while(cnt&&y[cnt]<=a[i].y) cnt--;//有i>k 必有 a[i].x>=a[k].x 
        x[++cnt]=a[i].x;y[cnt]=a[i].y;//如果a[i].y>=a[k].y 那就可以把k再见了,否则不行 
    } //所以操作完后 k >= i 时    必有x[k]>=x[i] 与y[k]<y[i] 因为如果y[k]>x[i] 那么i就再见了 
    //如果此时i与k分到一起 代价为 x[k]*y[i] 所以x递增 y递减 

/*  O(n^2)  
    f[i]表示包含i以前的分成几组 
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                f[i]=min(f[i],f[j]+y[j+1]*x[i]);//显然y[j+1]是[j+1,i]中y最大的 
            }                                   //x[i] 是 [j+1,i] 中x最大的,中间的都分到这一组 
        }
*/
    q[++tail]=0;
    for(int i=1;i<=cnt;++i){
        while(head<tail&&(MZ(q[head+1],q[head])<x[i])) head++;
//      printf("%d\n",head) ;
        F[i]=F[q[head]]+y[q[head]+1]*x[i];
        while(head<=tail&&(MZ(q[tail],q[tail-1])>(MZ(i,q[tail])))) tail--;
        q[++tail]=i;
    }
    printf("%lld",F[cnt]);
    return 0;
}
本文链接:http://www.mayflyyh.com/archives/206
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
没有标签
首页      未分类      bzoj1597: [Usaco2008 Mar]土地购买
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

  • http://2.gravatar.com/avatar/?s=80&d=monsterid&r=g
    Nicky

    Why did you come to ? can you use tramadol and ibuprofen together Couples with dual incomes but no kids, or “Dinks,” are on the rise in Mexico, nearly doubling since 2005. They are buoying a growing high-end goods market, splashing out on everything from expensive lingerie to home decor.

    6小时前回复
  • http://0.gravatar.com/avatar/?s=80&d=monsterid&r=g
    Taylor

    I need to charge up my phone patanjali divya pharmacy online No one should overlook their usefulness in forcing voters to make a choice between competing visions of what candidates believe about government, about what it is supposed to permit and about what government should do. Usually though, the ones complaining the loudest are the ones who are on the receiving end of the punch. They yell because it hurts.

    6小时前回复
  • http://0.gravatar.com/avatar/?s=80&d=monsterid&r=g
    pdewcfoudbq

    gTJR9y wstxyqyhqdbr, [url=http://qrffqtpwukiu.com/]qrffqtpwukiu[/url], [link=http://xuzseapgqcbb.com/]xuzseapgqcbb[/link], http://xgfdvhmapbom.com/

    2天前回复

MayFlyyh's Blog

bzoj1597: [Usaco2008 Mar]土地购买
bzoj1597: [Usaco2008 Mar]土地购买 Description 农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 < = 1,000…
扫描二维码继续阅读
2018-05-17