用動態規劃求解該問題：
題目描述：
游戲"憤怒的小鳥"，各位仙家都玩過了吧，俗話說：“飛得越高，砸得更狠”，各小鳥們在游戲中簡直是各顯神通，競相飛得更高，哪怕是粉身碎骨，但求美名留人間。
為了獲得更高的飛越高度，小鳥們不知從何處得到了一批神力大補丸，吃了這些大補丸將可以幫助小鳥們獲得更高的飛行高度。不幸的是，不知道那個該死的叛徒走漏了訊息，可惡的綠豬獲得了這個情報，于是他們賄賂了當地的一個巫師，希望巫師從中作梗為難小鳥們，于是巫師連夜在這批大補丸上施加了一種可怕的詛咒，就是小鳥們在服用這些大補丸時，當吃到到奇數個大補丸會增加飛行功力（增加值為該大補丸的“藥力”值）；吃到偶數個大補丸會降低飛行功力（降低值也是該大補丸的“藥力”值），當然小鳥們在挑選時可以跳過某些大補丸不吃。小鳥們有點犯難，雖然說只要謹慎挑選是可以確保吃了這批大補丸后能得到功力的提升，但神力大補丸之所以稱為神力，那可是花了高價錢好不容易才搞到手的，怎么可以隨便處理了事。有沒有一種選擇方案可以讓這批神力大補丸發揮最大的藥效呢？
幸好，小鳥們有個當程式員的朋友，也就是你，他們現在求助于你，那么你能找到一種選擇方案可以讓這批神力大補丸發揮最大的藥效嗎？
輸入：
輸入有多組用例，對每組用例：
第1行：一個整數n（1<=n<=150,000），表示大補丸的數量
第2行：包含n個整數pi（1<=pi<=500），每個整數表示一個大補丸的“藥力”值。假設小鳥們只能按這個給定的次序依次挑選大補丸。
輸出：
第1行：一個整數，食用這批神力大補丸后能達到的最大的藥效。
輸入樣例：
8
7 2 1 8 4 3 5 6
12
51 141 41 152 79 72 28 145 41 26 176 78
輸出樣例：
17
519
uj5u.com熱心網友回復：
dp1[i], dp2[i] 0<= i <=ndp1 吃掉第j個時， 并且已經吃了奇數個，得到的最大量
dp2 吃掉第j個時，并且已經吃了偶數個獲得的最大值
狀態就這樣，轉移方程就很明顯了
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/60163.html
標籤：C++ 語言