魔力屏障 (magic)
【問題描述】
小 Z 生活在神奇的魔法大陸上，今天他的魔法老師給了它這樣一個法陣作為它 的期末考試題目： 法陣由從左至右 n 道魔力屏障組成，每道屏障有一個臨界值 a，如果它承受攻 擊的魔力值 ≥ a，屏障將會破碎，它所承受的魔力攻擊將在魔力值減半后（向下取 整）繼續向右移動，否則該攻擊會被該屏障完全攔截，停留在屏障前，屏障的臨界 值不會減少，當兩次攻擊相遇時，兩次攻擊會疊加形成新的攻擊，新的攻擊的魔力 值為兩次攻擊魔力值之和，新的攻擊會繼續向右移動，小 Z 可以在法陣中任意一個 位置釋放任意大小魔力值的攻擊，攻擊會向右移動直到遇到一個還未被摧毀的屏障 或離開法陣， 對于所有 1 ≤ i ≤ n ，小 Z 希望用最小的法力值使得第 1 ～ i 道屏障全部破碎，
【輸入格式】
第一個一個正整數 n 表示屏障的數量， 第二行 n 個正整數，第 i 個數為第 i 道屏障的臨界值，
【輸出格式】
一行 n 個數，第 i 個表示使第 1 ～ i 道屏障全部破碎的最小法力值，兩個數之 間用一個空格隔開，
【樣例 1 輸入】
5 10 3 3 8 4
【樣例 1 輸出】
10 10 11 17 17
【樣例 1 解釋】
對于 i = 1 ～ 3，直接從左到右釋放攻擊使得屏障恰好破碎，例如 i = 3 時依次 在屏障 1 ～ 3 上釋放魔力值為 10, 0, 1 的攻擊，對于 i = 4, 5 的方案，先在第 3 道屏 障上釋放魔力為 2 的攻擊，再在第 2 道屏障上釋放魔力為 3 的攻擊，此時屏障 2, 3 都已被破碎，屏障 4 上留有魔力值 1 的攻擊，此時再在第 1 道屏障上釋放魔力為 10 的攻擊，在第 4 道屏障上釋放魔力為 2 的攻擊，第 4, 5 道屏障都被擊碎，
【樣例 2】
見選手目錄下的 magic2.in 與 magic2.ans， 該樣例與子任務 2 滿足同樣的約束條件，
【樣例 3】
見選手目錄下的 magic3.in 與 magic3.ans， 該樣例與子任務 3 滿足同樣的約束條件，
【樣例 4】
見選手目錄下的 magic4.in 與 magic4.ans， 該樣例與子任務 4 滿足同樣的約束條件，
【資料規模與約定】
本題開啟子任務測驗，對于所有資料滿足 1 ≤ n ≤ 70, 1 ≤ ai ≤ 150， 子任務編號 分值 n ≤ ai ≤ 子任務依賴 1 30 10 5 無 2 20 20 10 1 3 20 70 2 無 4 30 70 150 2,3
總結：
最開始我想就是區間DP，狀態也是 f[i][j][k] 表示打完 i-j 還剩 k 的能量，
但我最開始想法是用前部分的剩余能量的一部分攻擊后半部分的能量，但這其實不好處理前半部分剩余能量的一部分，
正解是用前半部分的剩余能量全部留下，和后半部分的一起留下成為一坨新的能量一起留給后面，
當然也有前半部分的剩余能量攻擊后半部分的情況，但攻擊只會攻擊一個屏障，可以特殊判定一下 [i-j] 被分割為 [i-j-1] 和 [j] 兩個部分，前部分剩余能量攻擊 j ,仔細想想這樣可以包含完全部情況
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554090.html
標籤：其他
下一篇：返回列表