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 w₁ and height h₁ will fit in another doll of width w₂ and height h₂ if and only if w₁ < w₂ and h₁ < h₂ . 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 1t20 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 w₁, h₁, w₂, h₂,..., w_m, h_m , where w_i is the width and h_i is the height of doll number i . 1w_i, h_i10000 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 的條件是 !(w₁ < w₂ and h₁ < h₂)
那反過來就是 w₁ >= w₂ or h₁ >= h₂ , 藉由 dp 的概念後，因為是 "or"，發現這兩個並無關連。
因此需要一個查找 [w₂ , 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
*/