Description

The Build n‘ Profit construction company is about to build its tallest building. It will be huge, the tallest building in the world by a wide margin. It will house hundreds of thousands of people and have rocket-powered elevators to the upper floors. They even plan for a shuttle docking station instead of a helipad on its roof. But any building of that size is extremely costly to build and maintain, and even after selling and renting out all the floor-space it will be very difficult to meet the costs. Luckily, they have come up with a great solution. They will place advertisements on the outer walls of the building for a hefty charge. This will help offset some of the costs and bring in a profit.

However, feedbacks from prospective buyers of this advertisement space have brought up a new problem. Each customer wants a specific sized advertisement placed at a specific height, and they will pay a certain amount of money for it. Each advertisement order specifies its position (i.e. the lowest floor of the advertisement) and its size (i.e. the number of floors it covers, including the starting floor). Each advertisement spans the whole face of the building, so no two advertisements can occupy the same floor and no floors can be partially covered. Each order also includes the amount to be earned if that advertisement is placed on the building. Of course, no money is earned if only part of an advertisement is placed, or it is placed in any other position.

Since many of the advertisements want some of the same floors as others, it is often impossible to choose all of them. Can you help choosing which of the orders to accept so that the above constraints are fulfilled and the amount of profit is maximized?

Input

The first line of input will contain T (≤ 50) denoting the number of cases.

Each case starts with an integer N (1 ≤ N ≤ 30000) denoting the number of advertisement orders. Each of the next N lines represents an advertisement by three integers A (0 ≤ A ≤ 10⁵), B (1 ≤ B ≤ 10⁵) and C (1 ≤ C ≤ 1000) denoting the lowest floor, the number of floors the advertisement covers (including the lowest floor) and the amount of money earned for placing it, respectively.

Output

For each case, print the case number and the maximum profit they can achieve.

题意：给你n 个广告板，每个都有起始的位置，和它的跨度，以及利润，让你求最大的利润

思路：首先按高度排序后，设dp[i]表示到第i个时候的最大值，对于第i个考虑的它的前i-1个，找到终点最接近它起始位置的那块

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 30005;

struct Node {
	int a, b, c;	
	bool operator <(const Node &tmp) const {
		return b < tmp.b;
	}
} arr[maxn];
int dp[maxn];

int main() {
	int t, n;
	int cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d%d", &arr[i].a, &arr[i].b, &arr[i].c);
			arr[i].b += arr[i].a - 1;
		}
		sort(arr+1, arr+1+n);
		dp[0] = 0;
		for (int i = 1; i <= n; i++) {
			int h = arr[i].a - 1;
			int l = 0, r = i-1, k = -1;
			while (l <= r) {
				int m = l + r >> 1;
				if (arr[m].b <= h)
					l = m + 1, k = m;
				else r = m-1;
			}
			dp[i] = max(dp[i-1], dp[k] + arr[i].c);
		}
		printf("Case %d: %d\n", cas++, dp[n]);
	}
	return 0;
}

UVA - 11908 Skyscraper,布布扣,bubuko.com

UVA - 11908 Skyscraper

原文：http://blog.csdn.net/u011345136/article/details/38491515