首页 > 代码库 > hdu2652——Warching TV

hdu2652——Warching TV

2024-08-07 12:31:17   211人阅读

Warching TV

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 185    Accepted Submission(s): 67


Problem Description
Lemon likes warching TV very much. When winter holiday comes, it is a good time, isn’t it. There are lots of TV program listed on the paper. Every TV program has its start time ,end time, and the happiness value that will add Lemon’s happiness and it depends on Lemon’s taste.
 

Input
There are many test cases. Please process to end of file. Each test case starts with one integer N (1 <= N <= 100000) which indicates the size of the list of the TV program. Then N lines follow, each line contains three integers s, e and v. s, e indicate that the TV program is during [s, e](1 <= s <= e <= 1000000). v indicates that after warching the TV program will add Lemon v happyiness(1 <= v <= 1000). Once Lemon choose a TV program, he must finish warching the TV program.
 

Output
Print the maximum happiness value that Lemon will get.
 

Sample Input
2
1 2 1
3 4 2
2
1 2 1
2 4 2
 

Sample Output
3
2
 

Author
lemon
 

Source
决战龙虎门
 

Recommend
yifenfei   |   We have carefully selected several similar problems for you:  2658 2655 2656 2670 2650 
 

dp[i]表示处理到第i个节目的时候的最大值
dp[i] = max(dp[i - 1], dp[j] + v[i]);
分别对应不看第i个节目， 看第i个节目时最大的收获，由于每一步都是子问题的最优解，所以决策的时候可以二分查找答案（子问题具有单调性）

#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 = 100010;

struct node
{
	int l, r, w;
}inter[N];
int dp[N];

int cmp(node a, node b)
{
	if (a.r != b.r)
	{
		return a.r < b.r;
	}
	return a.l < b.l;
}

int main()
{
	int n;
	while(~scanf("%d", &n))
	{
		memset (dp, 0, sizeof(dp));
		for (int i = 0; i < n; ++i)
		{
			scanf("%d%d%d", &inter[i].l, &inter[i].r, &inter[i].w);
		}
		sort (inter, inter + n, cmp);
		dp[0] = inter[0].w;
		for (int i = 1; i < n; ++i)
		{
			dp[i] = inter[i].w;
			int l = 0, r = i - 1, mid, ans = -1;
			while (l <= r)
			{
				mid = (l + r) >> 1;
				if (inter[mid].r < inter[i].l)
				{
					ans = mid;
					l = mid + 1;
				}
				else
				{
					r = mid - 1;
				}
			}
			if (ans != -1)
			{
				dp[i] = max(dp[i], dp[ans] + inter[i].w);
			}
			dp[i] = max(dp[i], dp[i - 1]);
		}
		printf("%d\n", dp[n - 1]);
	}
	return 0;
}


hdu2652——Warching TV


联系
我们