TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

96.6% (28/29)

Submission's AC Ratio

60.3% (38/63)

Description

給你一個序列, 請你求出LIS

等等!你以為我會叫你求Longest Increasing Subsequence嗎?
天下才沒有這種好事咧!

我要你求的是Least Increasing Subsequences!

你該不會又天真的認為這是"最短遞增子序列吧",那你又錯了!
我雖然善良但也沒有這麼善良

你的任務,事實上,是把這個序列分成其若干個子序列
其中每一個都是嚴格遞增子序列

Input Format

每次輸入只有一組測試資料

第一行為一整數n,代表序列項數
接下來有n個以空格或換行分隔的數字,依序代表每項的值。

1 <= n <= 200
你可以假設合理地用int運算不會出問題。

Output Format

請輸出一個整數,代表至少要分成幾個序列。

Sample Input

21
1 2 5 3 9 11 7 12 8 18 19 20 13 14 21 22 19 23 24 28 25

Sample Output

2

Hints

分成1,2,3,7,8,13,14,19,25
 和5,9,11,12,18,19,20,21,22,23,24,28

Problem Source

原TIOJ1240 / TIOJ例行賽IV, Problem Setter: kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536