【题目大意】
给定一个长度为$n$的序列，求最长上升子序列的长度。
【思路分析】
设$f_i$表示长度为$i$的上升子序列末尾数的最小值。
对于数列中的每一个数$x$，我们要找到最小的$f_i$，并且保证$f_i\ge x$，更新$f_i=x$。若已有的$f$数组中没有任何一个$f_i$满足$f_i\ge x$，那么就$f_{max_i+1}=x$。
然后我们可以发现$f$数组有一个神奇的性质，就是保证单调递增，于是我们可以稍微优化一下？
后面的等我想起来再写吧QAQ
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define g() getchar() 7 #define rg register 8 #define go(i,a,b) for(rg int i=a;i<=b;i++) 9 #define back(i,a,b) for(rg int i=a;i>=b;i--) 10 #define db double 11 #define ll long long 12 #define il inline 13 #define pf printf 14 using namespace std; 15 int fr(){ 16 int w=0,q=1; 17 char ch=g(); 18 while(ch<'0'||ch>'9'){ 19 if(ch=='-') q=-1; 20 ch=g(); 21 } 22 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 23 return w*q; 24 } 25 int n,a[1002],f[1002],ans=1; 26 int main(){ 27 //freopen("","r",stdin); 28 //freopen("","w",stdout); 29 n=fr(); 30 go(i,1,n) a[i]=fr();f[1]=a[1]; 31 go(i,2,n){ 32 if(f[ans]<a[i]) {f[++ans]=a[i];continue;} 33 go(j,1,ans) 34 if(f[j]>=a[i]) {f[j]=a[i];break;} 35 } 36 pf("%d\n",ans); 37 return 0; 38 }