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; }