caioj1064 最长上升子序列

【题意】 有n个不相同的整数组成的数列，记为: a(1)、a(2)、……、a(n) 例如：3，18，7，14，10，12，23，41，16，24。  上例中挑出：3，18，23，24就是一个长度为4的上升序列， 如果挑出：  3，7，10，12，16，24长度为6的上升序列。 求出最长的上升序列的长度。 【输入格式】 第一行一个整数n（1<=n<=1000) 下来n个整数。 【输出格式】 最长上升子序列的长度。 【样例输入】 10 3 18 7 14 10 12 23 41 16 24 【样例输出】

6

非常经典的dp入门题【我也不知道我为什么还在写这个

关键：设 f [ i ] 为到第 i 位的最长上升子序列的长度

f [ i ] 一定是从第 i 位之前的比a [ i ] 小的子序列的长度推过来的

那么我们希望 这个长度越长越好

所以每一部都取max

f数组的初始值为1

最长上升子序列最短是1 就是它本身

#include<iostream> #include<cstdio> using namespace std; template <typename T> void read(T &x){ x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0'; x*=f; } int a[1111]; int f[1111]; int ans=-1; int main(){ int n; read(n); for(int i=1;i<=n;++i){ read(a[i]); f[i]=1; } for(int i=2;i<=n;++i){ for(int j=1;j<i;++j){ if(a[j]<a[i]) f[i]=max(f[i],f[j]+1); } ans=max(ans,f[i]); } cout<<ans<<endl; return 0; }