Codeforces Beta Round 4 (Div. 2 Only) 4D. 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.

Input

The first line contains integers n, w, h (1  ≤ n ≤ 5000, 1 ≤ w,  h  ≤ 106) — 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 ≤ 106).

Output

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.

样例：

Input:

2 1 1
2 2
2 2

Output:

1
1 

Input:

3 3 3
5 4
12 11
9 8

Output:

3
1 3 2 

单词：（我是废物）

// envelope n. 信封
// chain n.链
// respectively adv. 各自，分别，依次为

思路：

这道题和 AcWing 1012. 友好城市 思路基本一致，建议先写一下AcWing的那道题，会ez一点。

简单来说，就是对于w，h分别为第一第二关键字排序，在保证w已经递增（非严格递增）的情况下，对h求最长上升子序列，同时记录一下pre值，方便后续回溯路径。

但是这道题的坑很多，首先就是必须保证严格单调递增和排序，这就需要去重，这里我用了一个hash表去写。

以及最后如果chain的size 等于0，直接输出一个0就行了，不需要再输出编号。（调了一个小时T_T ）

参考代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>using namespace std;const int N = 5010;int n, m, w, h;
struct env
{int w, h;int id;bool operator< (const env& t){return w != t.w ? w < t.w : h < t.h;}
}a[N];
unordered_map<long long, bool> st;int f[N], ans[N], pre[N];int main()
{cin >> n;for (int i = 0; i <= n; i++) {cin >> w >> h;if (w > a[0].w && h > a[0].h && !st[w * 1000000 + h]){a[m++] = { w, h, i };st[w * 1000000 + h] = 1;}}m--;sort(a + 1, a + m + 1);for (int i = 1; i <= m; i++){f[i] = 1;for (int j = 1; j < i; j++)if (a[i].h > a[j].h && a[i].w != a[j].w){f[i] = max(f[i], f[j] + 1);if (f[i] == f[j] + 1) pre[i] = j;}}int res = 0, p = 0;for (int i = 1; i <= m; i++){if (res < f[i]){res = f[i];p = i;}}cout << res << endl;int x = p, cnt = 0;while (pre[x] != 0){ans[cnt++] = x;x = pre[x];}ans[cnt++] = x;reverse(ans, ans + cnt);if (ans[0] == 0 && cnt == 1) return 0;for (int i = 0; i < cnt; i++) cout << a[ans[i]].id << ' ';return 0;
}