ZJU/ZOJ 2136 Longest Ordered Subsequence 解题报告

题目大意是求一个数列的最长上升序列长度。

因为序列长度n<=1000，所以用O(n^2)的经典最长上升序列模型DP即可。状态转移方程是f[i]=max(f[i],f[j]+1)(num[i]>num[j],1<j<i<=n)。其中f[i]表示从数列的第一个数到第i个数的最长上升序列的长度，num[i]表示第i个数。

3068393    2008-09-13 13:11:22    Accepted    2136    FPC    00:00.01    412K    IwfWcf@LZOI