a194: 死亡 FLAG
Tags : DAG DFS LIS 圖論
Accepted rate : 59人/157人 ( 38% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-12 22:45

Content

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

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

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

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

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

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

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

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

Input

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

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

Output
輸出當小光解完所有的題目時, 小光最少的休息次數
Sample Input #1
5
1 2 3 4 5
5
5 4 3 2 1
7
1 3 5 8 2 6 7
Sample Output #1
1
5
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 2.0s , <10M
Hint :

※ 待請 example 編輯題目內容

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

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

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

Tags:
DAG DFS LIS 圖論
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」