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

 
 
 

日志

 
 

bzoj 1107 POI2007 驾驶考试egz 线段树优化轮廓线DP  

2014-07-09 16:46:30|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题网上题解貌似不多的样子 于是就决定写一篇多骗点访问量233
首先有一个很明显的性质 ——以一条纵向路作为起点
那么如果它能到达所有的路 它一定能到达最左和最右两条纵向的路
为了方便统计这样的路的数量 我们可以将所有的边反向
这样对于不加边的情况 从最左出发和最右出发能到的纵向路的交集就是这样的路的数量
接下来就是DP过程了 由于这是轮廓线DP
我们可以用F[i]记录到第i条纵向路(的底端) 至少需要添加的边的数量
然后用线段树来更新到该条纵向路的每一个纵坐标至少需要添加边的数量
(注意这里为了卡常数 线段树上并不是记录的对应区间的最小值 
而是记录的对应的区间的最大的最小值)
后面的操作就比较简单了 细节可以参考代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=100010,T=270000;
struct edge
{
int x,y,d;
}a[N];
int firste[N],nexte[N],v[N];
int fl[N],fr[N],minnum[T],ml[N],mr[N];
int n,m,p,k,e=1,delta,num=0,ans=0;
void build_edge(int x,int y)
{
++e;
nexte[e]=firste[x];
firste[x]=e;
v[e]=y;
}
bool cmp(edge aa,edge bb)
{
return aa.y>bb.y;
}
void inquiry_seg(int x,int tl,int tr,int y)
{
if(tl==tr)
{
delta=minnum[x];
return;
}
minnum[x<<1]=imin(minnum[x],minnum[x<<1]);
minnum[x<<1|1]=imin(minnum[x],minnum[x<<1|1]);
int mid=(tl+tr)>>1;
if(y<=mid)inquiry_seg(x<<1,tl,mid,y);
else inquiry_seg(x<<1|1,mid+1,tr,y);
}
void change_seg(int x,int tl,int tr,int R)
{
if(R>=tr)
{
minnum[x]=imin(minnum[x],delta);
return;
}
minnum[x<<1]=imin(minnum[x],minnum[x<<1]);
minnum[x<<1|1]=imin(minnum[x],minnum[x<<1|1]);
int mid=(tl+tr)>>1;
if(R>mid)
change_seg(x<<1|1,mid+1,tr,R);
change_seg(x<<1,tl,mid,R);
}
void DP(int F[N])
{
for(int i=1;i<n;++i)
{
for(int p=firste[i];p;p=nexte[p])
{
inquiry_seg(1,0,m,v[p]);
--delta;
change_seg(1,0,m,v[p]);
}
inquiry_seg(1,0,m,0);
F[i+1]=i+delta;
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&p,&k);
rep(i,p)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
sort(a+1,a+1+p,cmp);
rep(i,p)
if(a[i].d)
build_edge(a[i].x,a[i].y);
DP(fl);
e=1;
memset(firste,0,sizeof(firste));
memset(minnum,0,sizeof(minnum));
rep(i,p)
if(!a[i].d)
build_edge(n-a[i].x,a[i].y);
DP(fr);
rep(i,n)
if((!fl[i])&&(!fr[n+1-i]))++num;
rep(i,n)
{
mr[fl[i]]=i;
ml[fr[i]]=i;
}
rep(i,k)
{
mr[i]=imax(mr[i],mr[i-1]);
ml[i]=imax(ml[i],ml[i-1]);
}
for(int i=0;i<=k;++i)
ans=imax(ans,ml[i]+mr[k-i]-n-num);
printf("%d",ans);
return 0;
}



  评论这张
 
阅读(376)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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