首页 > 代码库 > hdu 3016 Man Down (线段树 + dp)
hdu 3016 Man Down (线段树 + dp)
题目大意:
是男人就下一般层。。。没什么可以多说的吧。
注意只能垂直下落。
思路分析:
后面求最大值的过程很容易想到是一个dp的过程 。
因为每一个plane 都只能从左边 从右边下两种状态。
然后我们所需要处理的问题就是 ,你如何能快速知道往左边下到哪里,往右边下到哪里。
这就是线段树的预处理。
讲线段按照高度排序。
然后按照高度从小到大加入到树中。
然后去寻找左端点 和 右端点最近覆盖的线段的编号。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define mid ((s+e)>>1) #define maxn 100005 using namespace std; struct Line { int h,st,ed,v; bool operator < (const Line &cmp)const { return h<cmp.h; } }scline[maxn]; int cov[maxn<<2]; int ldn[maxn]; int rdn[maxn]; void pushdown(int num) { if(cov[num]) { cov[num<<1]=cov[num<<1|1]=cov[num]; cov[num]=0; } } int query(int num,int s,int e,int pos) { if(cov[num])return cov[num]; if(s==e)return 0; if(pos<=mid)return query(lson,pos); else return query(rson,pos); } void update(int num,int s,int e,int l,int r,int val) { if(l<=s && r>=e){ cov[num]=val; return; } pushdown(num); if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); } int dp[maxn]; int main() { int n; while(scanf("%d",&n)!=EOF) { int m=0;n++; scline[1].h=0,scline[1].st=1,scline[1].ed=maxn-1,scline[1].v=0; for(int i=2;i<=n;i++) { scanf("%d%d%d%d",&scline[i].h,&scline[i].st,&scline[i].ed,&scline[i].v); } m=maxn-1; sort(scline+1,scline+1+n); memset(cov,0,sizeof cov); for(int i=1;i<=n;i++) { ldn[i]=query(1,1,m,scline[i].st); rdn[i]=query(1,1,m,scline[i].ed); update(1,1,m,scline[i].st,scline[i].ed,i); } for(int i=1;i<maxn;i++)dp[i]=-0x3f3f3f3f; dp[n]=100+scline[n].v; for(int i=n;i>=1;i--) { if(dp[i]>0)dp[ldn[i]]=max(dp[ldn[i]],dp[i]+scline[ldn[i]].v); if(dp[i]>0)dp[rdn[i]]=max(dp[rdn[i]],dp[i]+scline[rdn[i]].v); } if(dp[1]>0)printf("%d\n",dp[1]); else puts("-1"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。