題目大意：求一個序列中不嚴格單調遞增的子序列的最小數目（子序列之間沒有交叉）。
這題證明貪心法可行的時候，可以發現和求最長遞減子序列的長度是同一個方法，只是思考的角度不同，具體證明並不是很清楚，這裡就給出貪心法的解題過程。
首先很容易想到的就是對n長度數列進行n次遍歷，每一次盡可能長地取出一個遞增序列，顯然這樣最後取出的序列數目是最少的。但是這是一個n^2的算法，如果數據取極端的完全遞減情況，很容易就能卡掉時間。Ps：這題的測試數據可能設計的並不是很嚴謹，這個簡單的貪心法只要開一個記錄已經取出序列的數組進行優化，就能AC了（而且更讓人無語的是南理的官方題解竟然沒用二分優化，用了個n^2的算法）。
既然n次遍歷數組太慢，那就得尋求一次遍歷就能讓所有元素都進入一個序列的方法。首先，若當前加入的元素，比前面某個元素小，那麼這個元素必定能加入某個序列而不用自成一個序列，這樣能保證序列盡可能的少。那麼問題來了，並不是隨便就能加進一個序列，比如前面有一個子序列3，5，6，現在進來一個元素4，雖然前面有個更小的3，但是這樣會相應地拆散前面的子序列，並沒有達到減少一個序列產生的目的。思考到這，應該不難想到，後面的元素能否加入前面的序列應當只和子序列的最大項有關，例如3，5，6這個序列，如果進來的元素是7，那麼就可以增長序列為3，5，6，7。
已經想到需要維護一個各序列的最大項的數組，那麼現在面臨的問題是在多個序列都可以加進當前元素的時候，往哪個序列加是最優的決策。（接下來是貪心法的核心思想）可以想象，如果前面已經有若干個序列序列，最大項分別是4，6，15，而當前需要加入的元素是20。發現，三個序列都能加進去，但是如果直接加入4為最大項的序列，那就意味著這個序列的最大項更新成20，變成20，6，15。那麼，如果後面再進來一個元素5，發現前面的子序列沒有一個能加進去，如果上一步把20加入了6或15，那就意味著現在的元素5是可以加入子序列，而不用產生新的序列。思考到這，貪心決策已經非常明顯了：如果當前元素能加入已有的序列，那麼應該加入當前元素大於的最大序列（通俗來講就是最大項比當前元素小，但是離得又是最近的子序列）。給出一個例子作為演示：
現在有序列5 7 10 3 1 8 4 6 9 2。
1、進入5，由於沒有已經存在子序列，自成序列：5。
2、進入7，搜索已有的比7小的最大序列，找到了5，更新：7。
3、進入10，同上一步，更新序列：10。
4、進入3，同上一部搜索，未找到符合條件的序列，自成一列：10 3。
5、進入1，同上自成一列：10 3 1。
6、進入8，搜索找到符合條件的3，更新序列：10 8 1。
7、進入4，同上，更新序列：10 8 4。
8、進入6，同上，更新序列：10 8 6。
9、進入9，同上，更新序列：10 9 6。
10、進入2，未找到符合條件的序列，自成一列：10 9 6 2。
程序結束，得到4個子序列分別是：5 7 10，3 8 9，1 4 6，2。
通過上面的模擬程序過程不難發現，其實維護子序列最大項就是一個單調棧，而且每一次對子序列的更新由於貪心決策，並不會破壞其單調的性質，所以這裡就有了優化，檢索符合條件的子序列時可以使用二分查找，最終程序的復雜度T（n） = O（n*logn）。
附上C++代碼（並不是AC代碼，為測試做過改動，能輸出各個子序列）
#include <cstdio>
#define FOR(i,x,y) for(int i = x; i <= y; ++i)
int t,n,top;
int pre[10010];
int ret[10010];
struct node
{
int data;
int index; //結構體加入index，用於逆向檢索，生成序列；
}a[10010];
node temp;
int Find(int l,int r) //二分查找符合的子序列；
{
int mid = (l + r) >> 1;
while(l < r)
{
if(temp.data > a[mid].data)
r = mid;
else if(temp.data < a[mid].data)
l = mid+1;
else return
mid;
mid = (l + r) >> 1;
}
return l;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
scanf("%d",&a[1].data);
a[1].index = 1;
ret[1] = a[1].data;
top = 1;
FOR(i,0,n)
pre[i] = i;
FOR(i,2,n)
{
scanf("%d",&temp.data);
temp.index = i;
ret[i] = temp.data;
if(a[top].data > temp.data) //如果比棧頂元素小，就直接壓棧；
{
++top;
a[top] = temp;
}
else
{
int cnt = Find(1,top); //檢索後，更新序列；
pre[i] = a[cnt].index;
a[cnt] = temp;
}
}
printf("%d\n",top); //最後棧的長度就是序列數；
for(int i = 1; i <= top; ++i) //倒序輸出所有序列，要正序需要數組或者遞歸輸出；
{
int k = a[i].index;
while(pre[k] != k)
{
printf("%d ",ret[k]);
k = pre[k];
}
printf("%d\n",ret[k]);
}
}
return 0;
}
