[UVA][dp、BIT] 11368 - Nested Dolls＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-05-07 10:54:36| 人2,706| 回0 | 上一篇 | 下一篇

[UVA][dp、BIT] 11368 - Nested Dolls

推 0 收藏 0 0 站台

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
*/