题目地址：Codeforces：Problem – 4D – Codeforces、洛谷：CF4D Mysterious Present – 洛谷 | 计算机科学教育新生态

题目描述

Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A = {a1,  a2,  …,  an}, where the width and the height of the i-th envelope is strictly higher than the width and the height of the (i  -  1)-th envelope respectively. Chain size is the number of envelopes in the chain.

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he’ll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It’s forbidden to turn the card and the envelopes.

Peter has very many envelopes and very little time, this hard task is entrusted to you.

题意简述

给定$n$个矩形，长宽分别为$w_i, h_i$。定义矩形的严格递增序列为一个序列$A = \{a_1, a_2, a_3, \dots, a_m\}$满足$w_{a_1} < w_{a_2} < w_{a_3} < \cdots < w_{a_m}, h_{a_1} < h_{a_2} < h_{a_3} < \cdots < h_{a_m}$。请从给定矩形中选出满足$w_i > w, h_i > h$的一些矩形，组成一个最长的严格递增序列。如果找不出任何符合条件的序列，则输出0。

输入输出格式

输入格式：
The first line contains integers n, w, h (1  ≤ n ≤ 5000, 1 ≤ w,  h  ≤ 10^6) — amount of envelopes Peter has, the card width and height respectively. Then there follow n lines, each of them contains two integer numbers wi and hi — width and height of the i-th envelope (1 ≤ wi,  hi ≤ 10^6).

输出格式：
In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 0 in the single line.

输入输出样例

输入样例#1：

2 1 1
2 2
2 2

输出样例#1：

1
1 

输入样例#2：

3 3 3
5 4
12 11
9 8

输出样例#2：

3
1 3 2 

题解

一眼过去，LIS的即视感，而且数据范围提示$O(n^2)$的普通LIS能跑过，那应该就是它了。
考虑到严格递增矩形序列一定是长宽都递增，那么按长为第一关键字，宽为第二关键字排序后直接在新序列上做LIS即可。

LIS的$O(n^2)$DP算法如下：
对于每一个位置$i$，向前找满足$w_j < w_i, h_j < h_i$的位置，并取$dp(j)$最大的位置，完成转移，即
$$ dp(i) = \max_{w_j < w_i, h_j < h_i} \{dp(j)\} + 1 $$

代码

// Code by KSkun, 2019/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    LL res = 0, neg = 1; char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 5005;

int n, w, h, dp[MAXN], pre[MAXN];
std::vector<int> ans;

struct Node {
    int w, h, no;
    bool operator<(const Node &rhs) const {
        return w == rhs.w ? h < rhs.h : w < rhs.w;
    }
} env[MAXN];

int main() {
    n = readint(); w = readint(); h = readint();
    for(int i = 1; i <= n; i++) {
        env[i].w = readint(); env[i].h = readint();
        env[i].no = i;
    }
    std::sort(env + 1, env + n + 1);
    for(int i = 1; i <= n; i++) {
        if(env[i].w <= w || env[i].h <= h) continue;
        int mxn = 0;
        for(int j = 1; j < i; j++) {
            if(env[j].w <= w || env[j].h <= h) continue;
            if(env[i].w > env[j].w && env[i].h > env[j].h && dp[j] > dp[mxn]) {
                mxn = j;
            }
        }
        dp[i] = dp[mxn] + 1; pre[i] = mxn;
    }
    int mxn = 0;
    for(int i = 1; i <= n; i++) {
        if(env[i].w <= w || env[i].h <= h) continue;
        if(dp[i] > dp[mxn]) mxn = i;
    }
    if(mxn == 0) {
        puts("0"); return 0;
    }
    printf("%d\n", dp[mxn]);
    int t = mxn;
    while(t != 0) {
        ans.push_back(env[t].no);
        t = pre[t];
    }
    std::reverse(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}