首页 > 代码库 > hdu3607——Traversal

hdu3607——Traversal

2024-08-06 15:45:11   214人阅读

Traversal

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1038    Accepted Submission(s): 365


Problem Description
Xiao Ming is travelling, and today he came to the West Lake, to see people playing a game, this game is like this, lake placed n-box, from 1 to n label. These boxes are floating in the water, there are some gold inside each box. Then participants from coast to jump the other side, each box have its’s height, you can only jump from lower height to higher height, and from a small label to a big label, you can skip some of the middle of the box. Suppose the minimum height is this side, the other side has the maximum height. Xiao Ming would like to jump how to get the most gold? He now needs your help.
 

Input
There are multiple test cases. Each test case contains one integer N , representing the number of boxes . The following N lines each line contains two integers hi and gi , indicate the height and the number of gold of the ith box.
1 < = N < 100 001
0 < hi < 100 000 001
0 < gi < = 10000
 

Output
For each test case you should output a single line, containing the number of maximum gold XiaoMing can get.

 

Sample Input
4
1 1
2 2
2 3
5 1

1 
1 10000
 

Sample Output
5
10000
 

Source
2010 ACM-ICPC Multi-University Training Contest（17）——Host by ZSTU
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  3397 3525 1698 1542 2871

简单的线段树dp
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N =  200010;
const int inf = -0x3f3f3f3f;
int dp[N];
int xis[N];
int n, cnt;
struct node
{
	int l, r;
	int val;
}tree[N << 2];

struct node2
{
	int g;
	int h;
}box[N];

int BinSearch(int val)
{
	int l = 1, r = cnt, mid;
	int ans;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (xis[mid] > val)
		{
			r = mid - 1;
		}
		else if (xis[mid] < val)
		{
			l = mid + 1;
		}
		else
		{
			ans = mid;
			break;
		}
	}
	return ans;
}

void build(int p, int l, int r)
{
	tree[p].l = l;
	tree[p].r = r;
	tree[p].val = inf;
	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 pos, int val)
{
	if (tree[p].l == tree[p].r)
	{
		tree[p].val = val;
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (pos <= mid)
	{
		update(p << 1, pos, val);
	}
	else
	{
		update(p << 1 | 1, pos, val);
	}
	tree[p].val = max(tree[p << 1].val, tree[p << 1 | 1].val);
}

int query(int p, int l, int r)
{
	if (l <= tree[p].l && tree[p].r <= r)
	{
		return tree[p].val;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (r <= mid)
	{
		return query(p << 1, l, r);
	}
	else if (l > mid)
	{
		return query(p << 1 | 1, l, r);
	}
	else
	{
		return max(query(p << 1, l, mid), query(p << 1 | 1, mid + 1, r));
	}
}

int main()
{
	while (~scanf("%d", &n))
	{
		int ans = 0;
		cnt = 1;
		xis[0] = 0;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d%d", &box[i].h, &box[i].g);
			xis[++cnt] = box[i].h;
		}
		sort (xis, xis + cnt + 1);
		cnt = unique(xis, xis + cnt + 1) - xis - 1;
		build(1, 1, cnt);
		dp[0] = 0;
		update(1, 1, dp[0]);
		for (int i = 1; i <= n; ++i)
		{
			int j = BinSearch(box[i].h), last;
			if (j == 1)
			{
				dp[i] = box[i].g;
			}
			else
			{
				last = query(1, 1, j - 1);
				dp[i] = last + box[i].g;
			}
			update(1, j, dp[i]);
			ans = max(ans, dp[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}


 

hdu3607——Traversal


联系
我们