poj 3903 Stock Exchange（最长上升子序列，模版题）

yywx001

　　题目
　　





#include<stdio.h>
//最长上升子序列 nlogn
//入口参数:数组名+数组长度，类型不限，结构体类型可以通过重载运算符实现
//数组下标从1号开始。
int bsearch(int a[],int len,int num)
{
int left=1,right=len;
while(left<=right)
{
int mid=(left+right)/2;
if(num<=a[mid])  //若最长不下降子序列，改<= 为 <
right=mid-1;
else
left=mid+1;
}
return left;
}
int LIS(int a[],int len)
{
int i,j,count=1;
int *dp=new int[len+1];
dp[1]=a[1];
for(i=2;i<=len;i++)
{
if(a>dp[count])    //若最长不下降子序列，改> 为 >=
dp[++count]=a;
else if(a<=dp[1])    //若最长不下降子序列，改<= 为 <
dp[1]=a;
else
dp[bsearch(dp,count,a)]=a;            
}
return count;
}
int aa[100099];
int main()
{
int t,i;
while(~scanf("%d",&t))
{
for(i=1;i<=t;i++)
scanf("%d",&aa);
printf("%d\n",LIS(aa,t));
}
return 0;
}
View Code