a194. 死亡 FLAG - 高中生程式解題系統

內容

最近小光解題總是不順利, 難題寫不出來也就算了, 連簡單題都得到一堆 WA

後來他發現當自己興致一來的時候, 寫得題目可以越來越難, 但是一寫到比之前還簡單的題目, 他就會立刻立起死亡 FLAG

這個時候只好先放下手頭上的題目, 休息一下再重新開始

但是小光對於解題總是有恐懼感, 他能很明確地排出哪道題目寫完, 後面的題目才解得出來, 接下來就交給你了

為了讓小光解題更加地順暢, 請你排完小光解題順序後, 輸出最少的休息次數

※　小光一開始上場前, 就有休息過了

在一旁解題的 example 就直接來吐槽了下, 你的解題方式簡直跟 LIS 一模一樣嘛,

只不過需要用最少不重疊的 LIS 覆蓋所有數列上的所有點罷了

輸入說明

有多筆測資, 每筆第一行, 有一個數字 N, 代表接下來有 N 個題目等待解題, (1 ≦ N ≦ 500)

下一行, 有 N 個數字 P, 代表題目難度(1 ≦ P ≦ 2147483647)

輸出說明

輸出當小光解完所有的題目時, 小光最少的休息次數

範例輸入 #1

5
1 2 3 4 5
5
5 4 3 2 1
7
1 3 5 8 2 6 7

範例輸出 #1

1
5
2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 2.0s , <10M

提示：

※　待請 example 編輯題目內容

第一筆測資: 休息 1 → 2 → 3 → 4 → 5

第二筆測資: 休息 5 休息 4 休息 3 休息 2 休息 1

第三筆測資: 休息 1 → 2 → 6 → 7 休息 3 → 5 → 8

標籤:

DAG DFS LIS 圖論

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」