hoj_10001_樸素DP（LIS）

Longest Ordered Subsequence

Time Limit: 1000ms, Special

Time Limit:2500ms, Memory Limit:32768KB

Total submit users: 1937,

Accepted users: 1621

Problem 10001 : No

special judgement

Problem

description

A

numeric sequence of ai is ordered if

a1 < a2 < ... <

aN. Let the subsequence of the given numeric sequence

(a1, a2, ...,

aN) be any sequence

(ai1, ai2,

..., aiK), where 1 <=

i1 < i2 < ... <

iK <= N. For example, sequence (1, 7, 3,

5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many

others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5,

8).

Your program, when given the numeric sequence, must find the

length of its longest ordered subsequence.

Input

The

first line of input contains the length of sequence N. The second line

contains the elements of sequence - N integers in the range from 0 to

10000 each, separated by spaces. 1 <= N <= 1000

Output

must contain a single integer - the length of the longest ordered

subsequence of the given sequence.

Sample

  這是求lis的一道題，也一個最基本的O(n*n)的一維DP，更是我算法之路的開始~~~~~~

  對于給定的a[N]數組，從1到n每次分别求對應a[i]的lis，最後即為最終的lis。

  AC代碼如下：