Posts Tagged ‘树状数组’

POJ 2047 Concert Hall Scheduling

Posted in PKU OJ on 四月 7th, 2010 by 纳米 – Be the first to comment

04-05：这水题怎么被分类到较难那里啊？！
04-05：好了我想错了……
04-06：终于构造得一个O(nt log t)的算法，依靠树状数组（t为最大天数）
04-07：发现之前改造程序的时候把排序错删了，提交，AC

简单题解：
根据请求的起始时间进行排序（其实起始时间和结束时间都没所谓的）。预处理，把所有时间段压缩为2 – t（所有时刻同时加减一个时刻，可以保持原有相对性。起始时间为2是方便树状数组编写需要）。
方程不好规范地写出了，大家意思意思，设f(x, y)为在某个请求下，音乐厅A[1, x]时间段被占用，音乐厅B[1, y]时间段被占用所能获得的最大利润。请求占用的时间段为[p, q]，可获得的利润为w。
有f(q, k) = max ( max{f(p – 1, k0) | 0 <= k0 <= k}, f(q, k) ), 0 <= k <= t
注意：枚举k需要从大到小。
这样，状态总数为O(n * t)，如果用普通实现的话，时间复杂度就是O(t)，那么总时间复杂度为O(n * t^2)，显然会超时。利用树状数组，可以把转移的时间复杂度降为O(log t)，所以，总时间复杂度为O(nt log t)。常数有点大，63ms通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
const int maxn = 1001, maxd = 369;
int n, m, data[maxn][3], pos[maxd][2], row[maxd][maxd];
 
bool input() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d%d", &data[i][0], &data[i][1], &data[i][2]);
	data[0][0] = data[0][1] = data[0][2] = 0;
	return n > 0;
}
 
int comp(int x[], int y[]) {
	return x[0] != y[0] ? x[0] - y[0] : x[1] - y[1];
}
 
int min(int x, int y) {
	return x < y ? x : y;
}
 
int max(int x, int y) {
	return x > y ? x : y;
}
 
int tree_select(int arr[], int w) {
	int res = 0;
	do {
		res = max(res, arr[w]);
		w -= w & -w;
	} while (w > 0);
	return res;
}
 
void tree_update(int arr[], int w, int x) {
	do {
		arr[w] = max(arr[w], x);
		w += w & -w;
	} while (w <= m);
}
 
int work() {
	qsort(data[1], n, sizeof(int) * 3, (int(*) (const void*, const void*)) comp);
	int mint = 365, maxt = 1, res = 0;
	for (int i = 1; i <= n; ++i) {
		mint = min(mint, data[i][0]);
		maxt = max(maxt, data[i][1]);
	}
	mint -= 2;
	m = maxt - mint;
	for (int i = 1; i <= n; ++i) {
		data[i][0] -= mint;
		data[i][1] -= mint;
	}
	memset(row, 0, sizeof(row));
	for (int k = 1; k <= n; ++k) {
		int t0 = data[k][0] - 1, t1 = data[k][1], w = data[k][2];
		for (int i = m; i > 0; --i) {
			int x = tree_select(row[i], t0) + w;
			tree_update(row[i], t1, x);
			tree_update(row[t1], i, x);
		}
	}
	for (int i = 1; i <= m; ++i)
		res = max(res, tree_select(row[i], m));
	return res;
}
 
int main() {
	while (input())
		printf("%d\n", work());
	return 0;
}