首页 > 代码库 > 【BZOJ】1537: [POI2005]Aut- The Bus
【BZOJ】1537: [POI2005]Aut- The Bus
【算法】DP+线段树求区间max(二维偏序)
【题解】
状态转移方程:f[i]=max(f[j]+v[i]),x[j]<x[i]&&y[j]<y[i]。
观察j的条件限制显然是二维偏序求最大值,套路化地离散化后一维排序+一维线段树即可解决。
最后在f[i]中找max,所以不用恢复原序。
复杂度O(n log n)。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> using namespace std; const int maxn=300010; int f[maxn],n,m,k; inline int max(int x,int y){return x>y?x:y;} struct lshs{int x,ord;}ls[maxn]; struct cyc{int x,y,v;}a[maxn]; struct tree{int l,r,mx;}t[maxn*2]; bool cmps(cyc a,cyc b){return a.x<b.x||(a.x==b.x&&a.y<b.y);} bool cmp(lshs a,lshs b){return a.x<b.x;} int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c==‘-‘)t=-1; do{s=s*10+c-‘0‘;}while(isdigit(c=getchar())); return s*t; } void lsh(){ for(int i=1;i<=k;i++)ls[i]=(lshs){a[i].x,i}; sort(ls+1,ls+k+1,cmp); int p=0; for(int i=1;i<=k;i++)if(ls[i].x==ls[i-1].x)a[ls[i].ord].x=p;else a[ls[i].ord].x=++p; n=p; for(int i=1;i<=k;i++)ls[i]=(lshs){a[i].y,i}; sort(ls+1,ls+k+1,cmp); p=0; for(int i=1;i<=k;i++)if(ls[i].x==ls[i-1].x)a[ls[i].ord].y=p;else a[ls[i].ord].y=++p; m=p; } void build(int k,int l,int r){ t[k].l=l;t[k].r=r; if(l==r)return; int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } void insert(int k,int x,int y){ if(t[k].l==t[k].r){t[k].mx=max(t[k].mx,y);} else{ int mid=(t[k].l+t[k].r)>>1; if(x<=mid)insert(k<<1,x,y); else insert(k<<1|1,x,y); t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx); } } int find(int k,int l,int r){ if(l<=t[k].l&&t[k].r<=r)return t[k].mx; else{ int mid=(t[k].l+t[k].r)>>1,mx=0; if(l<=mid)mx=find(k<<1,l,r); if(r>mid)mx=max(mx,find(k<<1|1,l,r)); return mx; } } int main(){ n=read();m=read();k=read(); for(int i=1;i<=k;i++){ a[i].x=read();a[i].y=read();a[i].v=read(); } lsh(); sort(a+1,a+k+1,cmps); build(1,1,m); for(int i=1;i<=k;i++){ f[i]=find(1,1,a[i].y)+a[i].v; insert(1,a[i].y,f[i]); } int ans=0; for(int i=1;i<=k;i++)ans=max(ans,f[i]); printf("%d",ans); return 0; }
【BZOJ】1537: [POI2005]Aut- The Bus
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。