首页 > 代码库 > HDU 3016 Man Down 线段树+简单DP
HDU 3016 Man Down 线段树+简单DP
囧,一开始看错题意,后来才发现人是垂直下落的,被附带链接里的Man Down游戏误导了。
那就变成了一个简单的DAG模型动态规划,随意搞就ok了
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_back#define lson rt << 1,l,mid#define rson rt << 1 | 1,mid + 1,rtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 1e5 + 10;struct Plank { int h,l,r,power; Plank(int h,int l,int r,int power): h(h),l(l),r(r),power(power) {} bool operator < (const Plank &p) const { return h < p.h; }};vector<Plank> plank;int n,Val[maxn << 2],lazy[maxn << 2];LL f[maxn];void pushdown(int rt) { if(lazy[rt] == -1) return; Val[rt << 1] = Val[rt << 1 | 1] = lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt]; lazy[rt] = -1;}void update(int rt,int l,int r,int ql,int qr,int v) { if(ql <= l && qr >= r) { Val[rt] = v; lazy[rt] = v; } else { int mid = (l + r) >> 1; pushdown(rt); if(ql <= mid) update(lson,ql,qr,v); if(qr > mid) update(rson,ql,qr,v); }}int query(int rt,int l,int r,int pos) { if(l == r) return Val[rt]; pushdown(rt); int mid = (l + r) >> 1; if(pos <= mid) return query(lson,pos); else return query(rson,pos);}int main() { int h,l,r,power,rb; while(scanf("%d",&n) != EOF) { plank.clear(); rb = -1; memset(f,0,sizeof(f)); memset(lazy,-1,sizeof(lazy)); for(int i = 0;i < n;i++) { scanf("%d%d%d%d",&h,&l,&r,&power); plank.PB(Plank(h,l,r,power)); rb = max(rb,r); } plank.PB(Plank(0,1,rb,0)); sort(plank.begin(),plank.end()); update(1,1,rb,1,rb,0); for(int i = 1;i <= n;i++) { int xl = query(1,1,rb,plank[i].l), xr = query(1,1,rb,plank[i].r); f[i] = max(f[xl],f[xr]) + plank[i].power; update(1,1,rb,plank[i].l,plank[i].r,i); } LL ans = f[n] + 100; ans = max(ans,-1LL); cout << ans << endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。