程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu2652——Warching TV

hdu2652——Warching TV

編輯：C++入門知識

hdu2652——Warching TV

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

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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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;
}