题目传送门
【题目大意】
给定一个长度为$n$的序列$\{a_n\}$，求最长上升子序列的长度。
【思路分析】
解法一：贪心(maybe?)
设$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$数组有一个神奇的性质，就是保证单调递增，于是我们可以稍微优化一下？
解法二：DP
设$f_i$表示以第$i$个数结尾的最长上升子序列的长度。
转移方程：$f_i=max\{f_j+1\}(a_i>a_j\&\&j\in[1,i-1])$，最后的答案为$max\{f_i\}(i\in[1,n])$
解法三
应该还有一种解法？但是我不记得了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 } 解法一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=0; 26 int main(){ 27 //freopen("","r",stdin); 28 //freopen("","w",stdout); 29 n=fr(); 30 go(i,1,n) a[i]=fr(),f[i]=1; 31 go(i,1,n){ 32 go(j,1,i-1) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1); 33 ans=max(ans,f[i]); 34 } 35 pf("%d\n",ans); 36 return 0; 37 } 解法二
转载于:https://www.cnblogs.com/THWZF/p/11542443.html
