p497. 00497 - Strategic Defense Initiative
標籤 :
通過比率 : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2025-05-12 06:48

內容

"指揮官!指揮官!趕快醒醒!"

"mmmm... 現在幾點了?"

"清晨 4:07,我們剛收到國防部的緊急電報,請指揮官裁示。"

你不甘願的拿過電報,揉揉眼睛,看到上面寫著:

``親愛的指揮官:

代誌大條了!昨天晚上俄羅斯瘋狂的 Boris 將軍伏特加喝多了,今天清晨時,原本要把鬧鐘按掉的,他......
我直接說好了,現在正有好幾枚洲際飛彈朝你那邊飛去。更不幸的是,我們只知道飛彈的高度以及到達
的順序。趕快去處理吧!祝你好運!
                                                                          國防部部長敬上
P.S. Hilly 和 Bill 要我和你說嗨!''

 

死啦!死啦!由於國防預算被刪減的緣故,你的愛國者反飛彈系統有嚴重的缺陷,發射的角度只能升不能降。也就是說,當你摧毀一枚來襲的飛彈之後,下一次你只能摧毀比上一枚飛得高的飛彈。例如:如果飛彈朝你飛來的高度分別是 1, 6, 2, 3, 5 (按照到達的順序),若你攔截了前 2 枚,那後面那 3 枚將無法再攔截。因為 2, 3, 5 都比 6 小。你的任務就是要攔截最多的飛彈數。

俄羅斯戰術非常奇怪,他們的將軍都是對數學準確非常執著的人。所以他們的飛彈總是以一種特別的順序來發射,使得上面所描述的問題只會有一組解答。

輸入說明

輸入的第 1 列有一個整數 𝑁,代表以下有幾組測試資料。然後空一列。接下來的各列每列有一個整數,代表來襲飛彈的高度 (按照飛彈到達的順序)。測試資料間空一列,請參考 Sample Input。

輸出說明

對每一組測試資料,請先輸出最多可以攔截幾枚飛彈。接下來的各列為所攔截到的飛彈的高度 (按照他們到達的順序)。測試資料間空一列,請參考 Sample Output。

範例輸入 #1
2

1
6
2
3
5

3
7
範例輸出 #1
Max hits: 4
1
2
3
5

Max hits: 2
3
7
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :
標籤:
出處:
UVa 497 [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

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