解題區/解題區 - UVa

UVa 12440 - Save the Trees

contents

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

Problem

有一排樹，每個樹分別有 type 和 height，現在要將其分團，

  • 每一團內不允許有相同的 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
*/