"指揮官!指揮官!趕快醒醒!"
"mmmm... 現在幾點了?"
"清晨 4:07,我們剛收到國防部的緊急電報,請指揮官裁示。"
你不甘願的拿過電報,揉揉眼睛,看到上面寫著:
``親愛的指揮官: 代誌大條了!昨天晚上俄羅斯瘋狂的 Boris 將軍伏特加喝多了,今天清晨時,原本要把鬧鐘按掉的,他...... 我直接說好了,現在正有好幾枚洲際飛彈朝你那邊飛去。更不幸的是,我們只知道飛彈的高度以及到達 的順序。趕快去處理吧!祝你好運! 國防部部長敬上 P.S. Hilly 和 Bill 要我和你說嗨!''
死啦!死啦!由於國防預算被刪減的緣故,你的愛國者反飛彈系統有嚴重的缺陷,發射的角度只能升不能降。也就是說,當你摧毀一枚來襲的飛彈之後,下一次你只能摧毀比上一枚飛得高的飛彈。例如:如果飛彈朝你飛來的高度分別是 1, 6, 2, 3, 5 (按照到達的順序),若你攔截了前 2 枚,那後面那 3 枚將無法再攔截。因為 2, 3, 5 都比 6 小。你的任務就是要攔截最多的飛彈數。
俄羅斯戰術非常奇怪,他們的將軍都是對數學準確非常執著的人。所以他們的飛彈總是以一種特別的順序來發射,使得上面所描述的問題只會有一組解答。
輸入的第 1 列有一個整數 𝑁,代表以下有幾組測試資料。然後空一列。接下來的各列每列有一個整數,代表來襲飛彈的高度 (按照飛彈到達的順序)。測試資料間空一列,請參考 Sample Input。
對每一組測試資料,請先輸出最多可以攔截幾枚飛彈。接下來的各列為所攔截到的飛彈的高度 (按照他們到達的順序)。測試資料間空一列,請參考 Sample Output。
2 1 6 2 3 5 3 7
Max hits: 4 1 2 3 5 Max hits: 2 3 7
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|