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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2298][HAOI2011]problem a  

2014-12-17 09:22:45|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2298: [HAOI2011]problem a

以前和别人讨论过的题……
当时想了好久恩
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
const int MAX = 1E9;
typedef pair<int,int> Data;
Data data[N],back[N];
bool operator < (Data &a,Data &b){return a.second == b.second?a.first<b.first:a.second<b.second;}
int n,m,dn,tree[N],num[N];
void push(int x,int val){for(x++;x<=n+1;x+=x&-x)tree[x] = max(tree[x],val);}
int get(int x){int re=0;for(x++;x;x-=x&-x)re = max(re,tree[x]);return re;}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
int main(){
int i,j,a,b;
n = scan();
for(i=1;i<=n;i++){
a = scan();b = scan();
if(a+b+1 > n)continue;
dn++;
data[dn] = back[dn] = Data(a+1,n-b);
}
sort(back+1,back+1+dn);
sort(data+1,data+1+dn);
m = dn;
dn = unique(data+1,data+1+dn)-data-1;
for(i=1,j=1;i<=dn;i++){
for(;j<=m&&data[i]==back[j];j++)num[i]++;
num[i] = min(num[i],data[i].second - data[i].first+1);
//printf("%d %d[%d]\n",data[i].first,data[i].second,num[i]);
}
int now = 0;
push(0,0);
for(i=1;i<=dn;i++){
a = get(data[i].first-1);
now = max(now,a+num[i]);
if(i!=dn && data[i+1].second!=data[i].second){
//printf("gonext\n");
push(data[i].second,now);
now = 0;
}
}
printf("%d\n",n-now);
return 0;
}

题解:
树状数组+DP
某个人认为有ai个人比他高bi个人比他低 == 他认为[ai+1, n-bi]这个区间里的人的分数相同。
问题就转换成选出尽可能多的不向交或完全重合的线段,
但是对于某条线段完全重合的个数要小于等于线段长。
树状数组维护一下前缀max就行了
  评论这张
 
阅读(129)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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