Mysterious Present

题面翻译

给出一个限制 $(w,h)$ 和 $n$ 个物品的二维信息$(w_i,h_i)$

求物品二维都满足 $w_i>w,h_i>h$ 的前提下的最长二维严格上升子序列以及其长度$(w_i>w_{i-1},h_i > h_{i-1}$ )

如果找不到任何一个物品满足条件 只需输出一行 0

( $1<=n<=5000$ , $1<=w,h<=10^{6},1<=w_{i},h_{i}<=10^{6}$ ).

分析

首先对于 $w_i\le w 且 h_j \le h$ 的 $i$ 不应当考虑。
接下来就是一个二维的最长上升子序列的问题了，可以对信封进行一个排序。
注意到 $n$ 的只有 $5000$ ，$O(n^2)$ 解决。 （绝对不是不会 $n log n$）

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, w, h, cnt, ans;
int d[N], p[N];

struct node{
    int w, h, id;
    bool operator<(node a){
        return w < a.w && h < a.h;
    }
    
} letter[N];

void P(int now){
    if (!now) return ;
    P(p[now]); cout << letter[now].id << " ";
}

signed main(){
    
    cin >> n >> w >> h;
    for (int i = 1, a, b; i <= n; i++){
        cin >> a >> b;
        if (a <= w || b <= h) continue;
        letter[++cnt] = {a, b, i};
    } n = cnt;
    
    if (!cnt){
        cout << 0;
        return 0;
    }
    
    sort(letter + 1, letter + 1 + n, [](node a, node b){
        return make_pair(a.w, a.h) < make_pair(b.w, b.h);
    });
    
    for (int i = 1; i <= n; i++)
        d[i] = 1;
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j < i; j++){
            if (letter[j].w < letter[i].w && letter[j].h < letter[i].h){
                if (d[j] + 1> d[i]){
                    d[i] = d[j] + 1;
                    p[i] = j;
                }
            }
        }
        if (d[i] > d[ans]){
            ans = i;
        }
    }
    
    cout << d[ans] << endl;
    P(ans);

    return 0;
}

Written with StackEdit中文版.