UVa 12440 - Save the Trees

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有一排樹,每個樹分別有 typeheight,現在要將其分團,

  • 每一團內不允許有相同的 type
  • 每一團的花費是最高的 height

計算總花費最小為何?

Sample Input

1
2
3
4
5
6
7
1
5
3 11
2 13
1 12
2 9
3 13

Sample Output

1
Case 1: 26

Solution

藉由掃描線的思路,可以得知每一個樹的位置 i,往左延伸最大多少內不會有重複的 type。詳見 12890 - Easy Peasy 的技巧。

因此會得到公式$dp([i]) = min(dp[j - 1] + max(height[k])), j \geq f(i), j \le k \le i$

dp[i]:將前 i 個樹分團的最少費用。

計算這個公式需要 O(n^2),由於 n 很大,必須找一個優化將其降下來。

首先知道 f(i) 是非遞減函數 (會一直增加),單純看 i 時,dp[j - 1] 是固定的,但
max(height[k]) 會逐漸增加,如果能在 O(log n) 時間進行更新、詢問,複雜度將可以降至 O(n log n)

每個元素有兩個屬性 (a, b)

  • query(f(i), i) : return min(A[k].a + A[k].b), f(i) <= k <= i
  • update(f(i), i, height[i]) : A[k].b = max(A[k].b, height[i])

左思右想仍然沒有辦法用線段樹完成它,至少是一個很 tricky 的花費計算。

有一個貪心的思路,考慮區間內的計算時,只需要找到嚴格遞減的高度進行更新即可,並非所有的可能進行嘗試。用一個單調隊列,只記錄 [f(i), i] 之間的嚴格遞減的高度資訊,接著每次需要窮舉單調隊列內的所有元素。

複雜度最慘還是 O(n^2),隨機測資下速度是快非常多的。

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int type[MAXN], height[MAXN];
long long dp[MAXN];
int dQ[MAXN];
int main() {
// freopen("in.txt", "r+t", stdin);
// freopen("out.txt", "w+t", stdout);
int testcase, cases = 0;
int n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d %d", &type[i], &height[i]);
map<int, int> R;
int L = 0;
dp[0] = 0;
int head = 0, rear = -1;
for (int i = 1; i <= n; i++) {
int &y = R[type[i]];
L = max(L, y);
y = i;
while (head <= rear && dQ[head] <= L)
head++;
while (head <= rear && height[dQ[rear]] <= height[i])
rear--;
dQ[++rear] = i;
dp[i] = 1LL<<60;
for (int j = head; j <= rear; j++) {
if (j != head)
dp[i] = min(dp[i], dp[dQ[j-1]] + height[dQ[j]]);
else
dp[i] = min(dp[i], dp[L] + height[dQ[j]]);
}
}
printf("Case %d: %lld\n", ++cases, dp[n]);
}
return 0;
}
/*
1
5
3 11
2 13
1 12
2 9
3 13
30
10
4 13
2 18
7 20
1 16
1 14
10 5
5 11
7 19
8 12
2 16
9999
10
10 16
3 5
8 11
8 2
5 3
6 2
10 19
6 10
6 16
6 4
9999
10
3 6
10 5
2 9
5 2
9 3
3 8
6 10
4 17
7 10
6 11
*/