Codeforces Gym101246H：``North-East''（LIS+思维）

http://codeforces.com/gym/101246/problem/H

题意：在二维平面上有n个点，从最左下角的点出发，每次走只能走在当前的点的右上角的点（x_j > x_i, y_j > y_i）。问在走了最长路径的前提下有哪些点是可能被走到的，哪些点是必须被走到的。

思路：比赛的时候以为是图论的题目，结果可以转化为LIS求解，太强啦。

首先直接对坐标按照x从小到大进行排序，如果x相同，y从大到小排序。为什么y是从大到小排序呢？因为在后面我们只看y的大小来做LIS，即通过排序消掉了x维，那么如果x相同的话，y小的在前面会使长度变大，但是此时的x是相同的，并不满足题意要严格在右上角的要求，如果y大的在前面就不会使得长度变长了。因此是从大到小排序。

做LIS，是为了得到一个数组：h[i]代表i这个点的LIS的长度是多少。这样就可以直接求解了。观察下面这样一个样例。

（每次画图都是画得很恶心）

我们知道，假设要从3走到4，那么3的y必须严格小于后面的4的y的，否则这个点是不可能走的。

这样我们看图中，7、8两点的4肯定是由6号点的3贡献的，因为4、5号点的3的y是大于等于后面所有的4的。

这样我们可以逆向思维，从后往前扫，对于每个LIS的长度维护一个最大的y值，用一个maxh[]数组表示。设求得LIS最长长度为len，长度为len的所有点都可能走到，当扫到长度为len-1的时候，只有y_i是小于maxh[len]才有可能走到，就这样扫到1。

还要解决哪些点必须走到，其实就是在可能走到的点里面，长度为h的点有且仅有一个的时候，这个点就必须走到，因为如果不走过这个点，就无法到达下一个长度为h+1的点了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 100010
 4 struct node {
 5     int x, y, id;
 6 } p[N];
 7 int n, len, h[N], maxh[N], dp[N], Hash[N];
 8 vector<int> maybe, must;
 9 
10 bool cmp(const node &a, const node &b) { if(a.x == b.x) return a.y > b.y; return a.x < b.x; }
11 
12 bool cp(const int &a, const int &b) { return p[a].id < p[b].id; }
13 
14 void LIS() { // 求解LIS
15     sort(p + 1, p + 1 + n, cmp);
16     dp[1] = p[1].y; h[1] = len = 1;
17     for(int i = 2; i <= n; i++) {
18         if(p[i].y > dp[len]) { dp[++len] = p[i].y; h[i] = len; }
19         int tmp = lower_bound(dp + 1, dp + 1 + len, p[i].y) - dp;
20         dp[tmp] = p[i].y; h[i] = tmp;
21     }
22 }
23 
24 void solve() {
25     // 处理出哪些是可能的
26     for(int i = 1; i <= n; i++) maxh[i] = -100000000;
27     for(int i = n; i >= 1; i--)
28         if(h[i] == len) { maxh[h[i]] = max(maxh[h[i]], p[i].y); maybe.push_back(i); }
29         else if(maxh[h[i]+1] > p[i].y) { maxh[h[i]] = max(maxh[h[i]], p[i].y); maybe.push_back(i); }
30     // 处理出哪些是必须的
31     for(int i = 0; i < maybe.size(); i++) Hash[h[maybe[i]]]++;
32     for(int i = 0; i < maybe.size(); i++)
33         if(Hash[h[maybe[i]]] == 1) must.push_back(maybe[i]);
34 
35     sort(maybe.begin(), maybe.end(), cp);
36     sort(must.begin(), must.end(), cp);
37     printf("%d ", maybe.size());
38     for(int i = 0; i < maybe.size(); i++) printf("%d ", p[maybe[i]].id); puts("");
39     printf("%d ", must.size());
40     for(int i = 0; i < must.size(); i++) printf("%d ", p[must[i]].id); puts("");
41 }
42 
43 int main() {
44     freopen("input.txt", "r", stdin);
45     freopen("output.txt", "w", stdout);
46     scanf("%d", &n);
47     for(int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i;
48     LIS();
49     solve();
50     return 0;
51 }