block code

#include<cstdio>
#include<cstring>
int a[50];
int n;
int ans(0);
int f[50];
int xt[50],cnt;
int find(int x)
{
int l=1,r=ans+1;
int m;
while(l<r)
{
m=l+(r-l)/2;
if(f[m]>x)
l=m+1;
else r=m;
}
return l;
}
int main()
{
n=1;
while(scanf("%d,",&a[n])==1)n++;
n--;
memset(f,0,sizeof(f));
int p;
for(int i=1;i<=n;i++)
{
p=find(a[i]);
if(p>ans)ans=p;
f[p]=a[i];
}
printf("%d,",ans);
cnt=1;
xt[1]=a[1];
for(int i=2;i<=n;i++)
{
int p=-1;
for(int j=1;j<=cnt;j++)
if(a[i]<=xt[j])
{
if(p==-1||xt[j]<xt[p])
p=j;
}
if(p!=-1)xt[p]=a[i];
else
{
cnt++;
xt[cnt]=a[i];
}
}
printf("%d",cnt-1);
return 0;
}

其实质就是把符合条件的LIS串成一条链，因为是LIS，所以这条链一定符合单调性。
那么我们for一遍，每次插入一个新的值x，如果x比链中最大（小）的都要大（小），那么一定是可以延展我的链的长度（因为我是顺着读的，已经有了基础的按位顺序），那么直接扩展我的链长度，把这个点加到链的最后面即可。如果不符合扩展条件，那么我们可以通过二分查找找到适合这个x用来更新的点的位置，然后更新即可。

求大神指点下nlogn的做法能不能统计最长不降子序列的方案数呢，需要怎样统计...

使用单调队列进行优化
如
5 6 9 1 3
的不上升自序列中
单调队列变化情况如下，再使用二分查找即可
5
5 6
5 6 9
1 6 9
1 3 9

up

up&help&thank you

up...