[UVA][dp、BIT] 11368 - Nested Dolls
G: Nested Dolls
| G: Nested Dolls |
Dilworth is the world's most prominent collector of Russian nested dolls: he literally has thousands of them! You know, the wooden hollow dolls of different sizes of which the smallest doll is contained in the second smallest, and this doll is in turn contained in the next one and so forth. One day he wonders if there is another way of nesting them so he will end up with fewer nested dolls? After all, that would make his collection even more magnificent! He unpacks each nested doll and measures the width and height of each contained doll. A doll with width w1 and height h1 will fit in another doll of width w2 and height h2 if and only if w1 < w2 and h1 < h2 . Can you help him calculate the smallest number of nested dolls possible to assemble from his massive list of measurements?
Input
On the first line of input is a single positive integer
1
t20
specifying the number of test cases to follow. Each test case begins with a positive integer
1m20000
on a line of itself telling the number of dolls in the test case. Next follow 2m
positive integers
w1, h1, w2, h2,..., wm, hm
, where wi
is the width and hi
is the height of doll number i
.
1wi, hi10000
for all i
.
Output
For each test case there should be one line of output containing the minimum number of nested dolls possible.
Sample Input
4 3 20 30 40 50 30 40 4 20 30 10 10 30 20 40 50 3 10 30 20 20 30 10 4 10 10 20 30 40 50 39 51
Sample Output
1 2 3 2
這題被歸類於 LIS，但題目卻求的是最少個數的 LIS 覆蓋所有數列元素。
但事實上這是很好轉換的，反求 LDS，則 LDS 就是答案。
那麼就可以在 O(nlogn) 之內求解。
這邊特別講另一個解法，最少路徑覆蓋，可以將這題轉換成最小路徑覆蓋的 DAG 圖，
但效率 O(n^3)，當然上不了場。
其實這題有點難處，因為算 LDS 的條件是 !(w1 < w2 and h1 < h2)
那反過來就是 w1 >= w2 or h1 >= h2 , 藉由 dp 的概念後，因為是 "or"，發現這兩個並無關連。
因此需要一個查找 [w2 , max_range] 元素中的最大值為何？同理對 h。
因此使用 Binary Indexed Tree 去做維護。
由於順序的關係，對 w 做升排序，對 h 做次降排序。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Rect {
int h, w;
bool operator<(const Rect &A) const {
if(A.h != h)
return h < A.h;
return w > A.w;
}
};
Rect D[20000];
int query(int idx, int arr[]) {
int ret = 0;
while(idx) {
ret = max(ret, arr[idx]);
idx -= idx&(-idx);
}
return ret;
}
void modify(int idx, int arr[], int L, int argv) {
while(idx <= L) {
arr[idx] = max(arr[idx], argv);
idx += idx&(-idx);
}
}
int main() {
int testcase;
int n, i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d %d", &D[i].h, &D[i].w);
}
sort(D, D+n);
int dp[20005] = {};
int wbit[10005] = {}, hbit[10005] = {};
int ret = 0;
for(i = 0; i < n; i++) {
int f1 = query(10005-D[i].h, hbit);
int f2 = query(10005-D[i].w, wbit);
dp[i] = max(dp[i], f1+1);
dp[i] = max(dp[i], f2+1);
modify(10005-D[i].h, hbit, 10005, dp[i]);
modify(10005-D[i].w, wbit, 10005, dp[i]);
ret = max(ret, dp[i]);
}
printf("%d\n", ret);
}
return 0;
}
/*
1000
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51
4
1 3 9 6 10 7 10 5
3
9 6 10 7 10 5
2
10 10 10 10
Output
1
2
3
2
2
2
2
*/