大三退役狗这段时间要准备几套题目来选拔省赛了，最近做题总是忘记贴题解？（变懒？）不管怎么样，自己还是勤快些吧。还有就是希望弱校今年省赛取得好成绩！
今天学弟在OJ上挂了一套给16级的选拔题目，我就去水了水。发现一道打印LIS的水题，感觉很有意思(^o^)/~，就记录一下吧。（线段树求解的方法就不说了）
\(dp[i]\)表示以\(a[i]\)结尾的LIS长度
\(g[i]\)表示长度为\(i\)的所有LIS里面最小的结尾元素
假设序列的LIS长度为\(ans\)，我们可以通过\(g[]\)找到一个可能的末尾元素\(g[ans]\)（有多个的话，当然选择距离序列末尾最近的），这样还需要从前面找出\((ans - 1)\)个元素。
寻找的过程中，每找到一个元素就将\(ans\)（当前LIS的剩余长度）减一。如果\(a[i]\)元素合法，那么一定有\(a[i]\)小于上一个元素且\(dp[i]\)等于当前LIS的剩余长度。
程序：
#include#include #include #include #include #include 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;}