解题思路:
注意事项:
参考代码:
#include<cstdio> #include<cstring> int a[100005],d[100005],n; int lis1() { int l,r=n,mid,cnt=0,ans; d[++cnt]=a[1]; for(int i=2;i<=n;i++) { if(a[i]<=d[cnt]) d[++cnt]=a[i]; else { l=1; r=cnt; while(l<=r) { mid=(l+r)>>1; if(d[mid]<a[i]) { ans=mid; r=mid-1; } else l=mid+1; } d[ans]=a[i]; } } return cnt; } int lis2() { memset(d,0,sizeof(d)); int l,r=n,mid,cnt=0,ans; d[++cnt]=a[1]; for(int i=2;i<=n;i++) { if(a[i]>d[cnt]) d[++cnt]=a[i]; else { l=1; r=cnt; while(l<=r) { mid=(l+r)>>1; if(d[mid]>=a[i]) { ans=mid; r=mid-1; } else l=mid+1; } d[ans]=a[i]; } } return cnt; } int main() { int ans; while(scanf("%d",&a[++n])==1); n-=1; printf("%d\n%d",lis1(),lis2()); }
0.0分
0 人评分
汽水瓶 (C语言代码)浏览:610 |
C二级辅导-公约公倍 (C语言代码)浏览:1510 |
矩形面积交 (Java代码)浏览:1222 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:517 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:675 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:604 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:968 |
WU-判定字符位置 (C++代码)浏览:1406 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:683 |
DNA (C语言代码)浏览:741 |