給你一個序列, 請你求出LIS
等等!你以為我會叫你求Longest Increasing Subsequence嗎?
天下才沒有這種好事咧!
我要你求的是Least Increasing Subsequences!
你該不會又天真的認為這是"最短遞增子序列吧",那你又錯了!
我雖然善良但也沒有這麼善良
你的任務,事實上,是把這個序列分成其若干個子序列
其中每一個都是嚴格遞增子序列
每次輸入只有一組測試資料
第一行為一整數n,代表序列項數
接下來有n個以空格或換行分隔的數字,依序代表每項的值。
1 <= n <= 200
你可以假設合理地用int運算不會出問題。
請輸出一個整數,代表至少要分成幾個序列。
分成1,2,3,7,8,13,14,19,25
和5,9,11,12,18,19,20,21,22,23,24,28
原TIOJ1240 / TIOJ例行賽IV, Problem Setter: kelvin
No. | Testdata Range | Score |
---|---|---|
1 | 0~13 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 200 | 65536 | 262144 | |
1 | 200 | 65536 | 262144 | |
2 | 200 | 65536 | 262144 | |
3 | 200 | 65536 | 262144 | |
4 | 200 | 65536 | 262144 | |
5 | 200 | 65536 | 262144 | |
6 | 200 | 65536 | 262144 | |
7 | 200 | 65536 | 262144 | |
8 | 200 | 65536 | 262144 | |
9 | 200 | 65536 | 262144 | |
10 | 200 | 65536 | 262144 | |
11 | 200 | 65536 | 262144 | |
12 | 200 | 65536 | 262144 | |
13 | 200 | 65536 | 262144 |