解題區/解題區 - UVa

UVa 12141 - Line Chart

contents

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

Problem

給 n 個點趨勢圖，可以選擇忽略某些點，忽略的點會被剩餘點補上靠左。

請問要恰好 k 個 peak 的情況，有多少不同的趨勢圖貌。這別要求兩個相鄰的點不可以有相同 y 值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
6 1
320 3
306 1
401 3
325 4
393 5
380 2
4 1
101 3
102 2
103 2
104 4
3 0
102 2
101 1
103 3

Sample Output

1
2
3
Case 1: 20
Case 2: 1
Case 3: 8

Solution

TLE 版本，答案是正確的。 O(n^2 m)

其實這有點接近貪心作法，狀態為 dp[i][k][3] 表示加入第 i 個點，產生 k 個 peak，並且下一次要接 y 值較高、較低、等於的點。

而考慮當前 k 個 peak y[i]，對於三種高地要求，我們只會轉移到不同的 y 值，也就是對於後面如果存有 y[p] = y[q], p < q，盡可能選擇 p 小的，否則會重複計算，要忽略 q 大的。

從下面樸素算法中，可以獲得基礎的遞迴公式。

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
#include <stdio.h> 
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
int dp[10005][64][3] = {};
const int mod = 1000000;
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout);
    int testcase, n, m, x, y;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        vector< pair<int, int> > D;
        map<int, int> R;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            R[y] = 0;
            D.push_back(make_pair(x, y));
        }
        sort(D.begin(), D.end());
        int v = 0;
        for (map<int, int>::iterator it = R.begin();
            it != R.end(); it++)
            it->second = v++;
        for (int i = 0; i < n; i++)
            D[i].second = R[D[i].second];
        memset(dp, 0, sizeof(dp));
        int used[10005] = {};
        for (int i = 0; i < n; i++) {
            if (used[D[i].second] == 0) {
                dp[i][0][0] = 1; // =
                dp[i][0][1] = 1; // <
                dp[i][0][2] = 1; // > next time
                used[D[i].second] = 1;
            }
        }
        int ret = 0;
        if (m == 0)
            ret++;
        for (int i = 0; i < n; i++) {
            ret = (ret + dp[i][m][0])%mod;
            memset(used, 0, sizeof(used));
//			for (int k = 0; k <= m; k++) 
//					printf("[%d %d] %d %d %d\n", i, k, dp[i][k][0], dp[i][k][1], dp[i][k][2]);
            for (int j = i+1; j < n; j++) {					
                if (used[D[j].second])	continue;
                used[D[j].second] = 1;
                for (int k = 0; k <= m; k++) {
                    if (D[j].second > D[i].second) { // larger
                        dp[j][k][0] = (dp[j][k][0] + dp[i][k][2])%mod;
                        dp[j][k+1][1] = (dp[j][k+1][1] + dp[i][k][2])%mod;
                        dp[j][k][2] = (dp[j][k][2] + dp[i][k][2])%mod;
                    } else if (D[j].second == D[i].second) {
//						dp[j][k][0] = (dp[j][k][0] + dp[i][k][0])%mod;
//						dp[j][k][1] = (dp[j][k][1] + dp[i][k][0])%mod;
//						dp[j][k][2] = (dp[j][k][2] + dp[i][k][0])%mod;
                    } else {
                        dp[j][k][0] = (dp[j][k][0] + dp[i][k][1])%mod;
                        dp[j][k][1] = (dp[j][k][1] + dp[i][k][1])%mod;
                        dp[j][k+1][2] = (dp[j][k+1][2] + dp[i][k][1])%mod;
                    }
                }
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}

使用 binary indexed tree 優化 O(nm log n)

使用前綴總和來完成狀態轉移。為了防止相同 y[p] = y[q], p < q，由於會先拜訪到 p 進行狀態轉移，特別考慮 y[q] 基底的轉移狀態必須被扣除 y[p] 的結果。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h> 
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
#include <assert.h>
using namespace std;
#define MAXN 10050
int dp[MAXN][64][3] = {};
int UBIT[64][3][MAXN], DBIT[64][3][MAXN];
int shift[64][3][MAXN] = {};
const int mod = 1000000;
int query(int A[], int idx) {
    int sum = 0;
    while (idx)
        sum = (sum + A[idx])%mod, idx -= idx&(-idx);
    return sum;
}
void modify(int A[], int idx, int val, int L) {
    while (idx <= L)
        A[idx] = (A[idx] + val)%mod, idx += idx&(-idx);
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout);
    int testcase, n, m, x, y;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        vector< pair<int, int> > D;
        map<int, int> R;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            R[y] = 0;
            D.push_back(make_pair(x, y));
        }
        sort(D.begin(), D.end());
        int L = 1;
        for (map<int, int>::iterator it = R.begin();
            it != R.end(); it++)
            it->second = L++;
        for (int i = 0; i < n; i++)
            D[i].second = R[D[i].second];
        memset(UBIT, 0, sizeof(UBIT));
        memset(DBIT, 0, sizeof(DBIT));
        memset(shift, 0, sizeof(shift));		
        int used[10005] = {};
        for (int i = 0; i < n; i++) {
            if (used[D[i].second] == 0) {
                shift[0][0][D[i].second] = -1; // =
                used[D[i].second] = 1;
            }
        }
        modify(UBIT[0][1], 1, 1, L);
        modify(UBIT[0][2], 1, 1, L);
        int ret = 0;
        if (m == 0)
            ret++;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k <= m; k++) {
                int dp0 = query(UBIT[k][0], D[i].second) + query(DBIT[k][0], L - D[i].second-1) - shift[k][0][D[i].second];
                int dp1 = query(UBIT[k][1], D[i].second) + query(DBIT[k][1], L - D[i].second-1) - shift[k][1][D[i].second];
                int dp2 = query(UBIT[k][2], D[i].second) + query(DBIT[k][2], L - D[i].second-1) - shift[k][2][D[i].second];
//				printf("[%d %d] %d %d %d\n", i, k, dp0, dp1, dp2);
                dp0 %= mod, dp1 %= mod, dp2 %= mod;
                shift[k][0][D[i].second] += dp0;
                shift[k][1][D[i].second] += dp1;
                shift[k][2][D[i].second] += dp2;
                if (k == m)		ret = (ret + dp0)%mod;
                if (dp2) {
                    modify(UBIT[k][0], D[i].second+1, dp2, L);
                    modify(UBIT[k+1][1], D[i].second+1, dp2, L);
                    modify(UBIT[k][2], D[i].second+1, dp2, L);
                }
                if (dp1) {
                    modify(DBIT[k][0], L - D[i].second, dp1, L);
                    modify(DBIT[k][1], L - D[i].second, dp1, L);
                    modify(DBIT[k+1][2], L - D[i].second, dp1, L);
                }
            }
        }
        printf("Case %d: %d\n", ++cases, (ret + mod)%mod);
    }
    return 0;
}
/*
3
3 0
1 1
2 1
3 1
3 1
101 3
102 2
104 4
3
6 1
320 3
306 1
401 3
325 4
393 5
380 2
4 1
101 3
102 2
103 2
104 4
3 0
102 2
101 1
103 3
*/