题目大意：求一个序列中不严格单调递增的子序列的最小数目（子序列之间没有交叉）。
这题证明贪心法可行的时候，可以发现和求最长递减子序列的长度是同一个方法，只是思考的角度不同，具体证明并不是很清楚，这里就给出贪心法的解题过程。
首先很容易想到的就是对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;
}