注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1113][Poi2008]海报PLA  

2015-01-29 13:09:12|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1113: [Poi2008]海报PLA

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 744  Solved: 449
[Submit][Status]

Description

N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

Input

第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering

Output

最少数量的海报数.

Sample Input

5
1 2
1 3
2 2
2 5
1 4
[BZOJ1113][Poi2008]海报PLA - Trinkle - n+e

Sample Output

4
[BZOJ1113][Poi2008]海报PLA - Trinkle - n+e

Solution

首先长没有用。

我们一列一列地读入数据。对于当前这一列(高为h),什么情况下不会增加答案呢?是左边有一列的高也为h,而且这两列之间的矩形都比h高。

这样的话我们维护一个单调不下降的栈。每次读入一个数,从栈顶往回把比这个数大的数都踢掉,如果最后栈顶的数和当前数一样,则不需要增加答案;否则这个数进栈,答案增加1

Code

/**************************************************************
    Problem: 1113
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:224 ms
    Memory:1228 kb
****************************************************************/
 
#include<cstdio>
inline int getc(){
    static char buf[1<<15],*S=buf,*T=buf;
    if(S==T)if(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)return 0;
    return*S++;
}
int aa,ch;inline int F(){
    while(ch=getc(),ch<48||ch>57);aa=ch-48;
    while(ch=getc(),ch>47&&ch<58)aa=aa*10+ch-48;return aa;
}
int n,i,x,ans,t,s[100010];
int main(){
    for(n=F(),s[0]=1<<31;n--;){
        F(),x=F();
        while(x<s[t])t--;
        if(x!=s[t])s[++t]=x,ans++;
    }
    printf("%d\n",ans);
}
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018