这道题是最长上升序列。

 

由于给出的数据量过大，不能直接使用dp的方法来去最长升序，因为这样的时间为0（n^2）

 

下面我们考虑如下的情况：

 

对于第i个数来说他是否是1……i的最长上升序列的元素，就是在1……i-1中的最长上升序列最后一个值比f[i]小，那么f[i]元素就为1……i上的最长上升序列的元素。

 

如过不存在1……i-1的最长上升序列满足上述情况时，我们不能直接认为i就1……n上的最长升序列。这是我们可以这样的假设，假设f[i]是1……n的最长生序列的元素。那么f[i]在1……n的最长升序列的位置应该在1……i-1的最长生序列中比f[i]小的最大的元素之后的位置k。当在i+1……n比x-k(x为1……i-1的最长上升序列的长度)大的时候,假设就成立。如果更新位置k上的值为f[i],最长上升序列的长度会变。所以可以用到贪心的思想。

 

代码如下：

 

 

#include <iostream>
#define maxn  40005
using namespace std;
int c[maxn];
int k;
void insert(int num)
{
 if(c[k-1]<num) c[k++]=num;
 else
 {
  int left=1,right=k-1;
  int mid=1;
  while(left!=right)
  {
   mid=(left+right)/2;
   if(c[mid]<num)
         left=mid+1;
   else
    right=mid;
  }
  c[left]=num;
 }
 return ;
}
int main()
{
 int n;
 cin >>n;
 while(n--)
 {
  k=1;
  int p;
  cin >>p;
  memset(c,0,sizeof(c));
  for(int i=0;i<p;i++)
  {
   int num;
   scanf("%d",&num);
   insert(num);
  }
  cout<<k-1<<endl;
 }
 return 0;
}