4 10 5 10 10 5 3 6 -100 4 7 11 20 2 2 1000 10
140
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
const int N = 100010;
const int inf = 0x3f3f3f3f;
int dp[N][2];
int n;
struct node
{
int l, r;
int h;
int w;
}blank[N];
struct node2
{
int l, r;
int h;
int col;
}tree[N << 2];
int cmp(node a, node b)
{
return a.h > b.h;
}
void build(int p, int l, int r)
{
tree[p].l = l;
tree[p].r = r;
tree[p].col = -1;
if (l == r)
{
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
}
void update(int p, int l, int r, int val)
{
if (l <= tree[p].l && tree[p].r <= r)
{
tree[p].col = val;
return;
}
if (tree[p].col != -1)
{
tree[p << 1].col = tree[p].col;
tree[p << 1 | 1].col = tree[p].col;
tree[p].col = -1;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (r <= mid)
{
update(p << 1, l, r, val);
}
else if (l > mid)
{
update(p << 1 | 1, l, r, val);
}
else
{
update(p << 1, l, mid, val);
update(p << 1 | 1, mid + 1, r, val);
}
}
int query(int p, int pos)
{
if (tree[p].l == tree[p].r)
{
return tree[p].col;
}
if (tree[p].col != -1)
{
tree[p << 1].col = tree[p].col;
tree[p << 1 | 1].col = tree[p].col;
tree[p].col = -1;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (pos <= mid)
{
return query(p << 1, pos);
}
else
{
return query(p << 1 | 1, pos);
}
}
int main()
{
while(~scanf("%d", &n))
{
memset (dp, -1, sizeof(dp));
int left = inf, right = -inf;
for (int i = 0; i < n; ++i)
{
scanf("%d%d%d%d", &blank[i].h, &blank[i].l, &blank[i].r, &blank[i].w);
left = min(left, blank[i].l);
right = max(right, blank[i].r);
}
// printf("%d %d\n", left, right);
build(1, left, right);
sort (blank, blank + n, cmp);
for (int i = n - 1; i >= 0; --i)
{
int j = query(1, blank[i].l);
if (j != -1)
{
dp[i][0] = max(dp[j][0], dp[j][1]) + blank[j].w;
}
else
{
dp[i][0] = 0;
}
j = query(1, blank[i].r);
if (j != -1)
{
dp[i][1] = max(dp[j][0], dp[j][1]) + blank[j].w;
}
else
{
dp[i][1] = 0;
}
update(1, blank[i].l, blank[i].r, i);
}
int ans = max(dp[0][0], dp[0][1]) + 100 + blank[0].w;
if (ans <= 0)
{
ans = -1;
}
printf("%d\n", ans);
}
return 0;
}原文:http://blog.csdn.net/guard_mine/article/details/41684695