今天学弟在OJ上挂了一套给16级的选拔题目，我就去水了水。发现一道打印LIS的水题，感觉挺有意思(^o^)/~，就记录一下吧。（线段树求解的方法就不说了）
dp[i] d p [ i ] 表示以 a[i] a [ i ] 结尾的LIS长度
g[i] g [ i ] 表示长度为 i i 的所有LIS里面最小的结尾元素
假设序列的LIS长度为ansans，我们可以通过 g[] g [ ] 找到一个可能的末尾元素 g[ans] g [ a n s ] （有多个的话，当然选择距离序列末尾最近的），这样还需要从前面找出 (ans−1) ( a n s − 1 ) 个元素。
寻找的过程中，每找到一个元素就将 ans a n s （当前LIS的剩余长度）减一。如果 a[i] a [ i ] 元素合法，那么一定有 a[i] a [ i ] 小于上一个元素且 dp[i] d p [ i ] 等于当前LIS的剩余长度。
程序：
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <stack> #include <algorithm> using namespace std; const int MAXN = 1e5 + 10; const int N = 1e9; typedef long long LL; const int INF = 15000000 + 10; int a[200100 + 10]; int dp[200100 + 10]; int g[200100 + 10]; int Stack[200100 + 10], top; int main() { int n; while(scanf("%d", &n) != EOF) { for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); g[i] = INF; } int ans = 0; for(int i = 1; i <= n; i++) { int id = lower_bound(g + 1, g + n + 1, a[i]) - g; dp[i] = id; g[dp[i]] = min(g[dp[i]], a[i]); ans = max(ans, dp[i]); } printf("%d\n", ans); top = 0; Stack[top++] = g[ans]; int N; for(int i = n; i >= 1; i--) { if(a[i] == g[ans]) { N = i; break; } } int mark = g[ans]; ans--; for(int i = N - 1; i >= 1; i--) { if(a[i] < mark && dp[i] == ans) { mark = a[i]; ans--; Stack[top++] = a[i]; } } for(int i = top - 1; i >= 0; i--) { printf("%d\n", Stack[i]); } } return 0; }