c470: 4th CPSC Problem 6-昕昕吃點心
標籤 :
通過比率 : 98% (39 人 / 40 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-02-12 15:48

內容

  你看過1980年代臺灣最火紅的連續劇──星星知我心嗎?

  昕昕是星星知我心的忠實觀眾,為了重現當時八點檔的熱潮,讓八點檔再次偉大,昕昕決定拍攝一部新的連續劇──昕昕吃點心!

  昕昕吃點心的劇情大致上是:昕昕出生於臺北是的窮困家庭,他最喜歡吃點心了,而他的另外六個兄弟姐妹也是如此。有一日,昕昕參加了抽獎活動,竟然幸運地中了頭獎──點心吃到飽!不過吃到飽也是有所條件的,吃到飽的活動規則很特別,昕昕的面前有一橫排共N個各式各樣的點心,昕昕要從左側吃起並向右吃,而當他吃了其中一個點心後,他就不能吃掉那個點心旁邊的點心。昕昕可以不斷的吃,但是不能回頭,直到吃完所有可以吃的點心或者肚子快要撐破為止。

  昕昕覺得,不能吃完全部的點心實在太可惜了,他希望能盡他所能在不違反規則的情況下吃掉最能滿足他的點心組合。於是,昕昕為每一個點心標上了對他來說的滿足度,並且希望能找到讓他最滿足的點心吃法。不過由於昕昕實在太愛吃點心了,過於短視近利的他,無法克制自己的慾望。因此,在跳過了一個點心之後,他就會忍不住吃掉下一個。也就是說,最左側的點心昕昕可以選擇跳過,不過下一個的點心昕昕就會忍不住把它吃掉。

  因為昕昕花了人生中一大半的時間研究吃點心的美好,導致數學跟程式設計都沒有學好,因此無法自己解決這個問題。很幸運地,昕昕遇到了聰明的你,請你幫他找出在不違反規則下最能滿足他的吃法的滿足度總和吧!

輸入說明

  輸入有兩行,第一行有一個正整數N,表示昕昕面前的點心數量。

  第二行包含N個正整數ai,表示從最左側數來第i個點心的滿足度。

 

  • 1 ≤ N ≤ 106
  • 1 ≤ ai ≤ 100
輸出說明

  輸出一個正整數,表示符合規則的所有吃法中,滿足度總和最高的吃法的滿足度總和值。

範例輸入
SAMPLE INPUT 1:
3
1 2 3

SAMPLE INPUT 2:
4
9 8 1 2
範例輸出
SAMPLE OUTPUT 1:
4

SAMPLE OUTPUT 2:
10
測資資訊:
記憶體限制: 256 MB
不公開 測資點#0 (2%): 1.0s , <1K
不公開 測資點#1 (2%): 1.0s , <1K
不公開 測資點#2 (2%): 1.0s , <1K
不公開 測資點#3 (2%): 1.0s , <1K
不公開 測資點#4 (2%): 1.0s , <1K
不公開 測資點#5 (2%): 1.0s , <1K
不公開 測資點#6 (2%): 1.0s , <1K
不公開 測資點#7 (2%): 1.0s , <1K
不公開 測資點#8 (2%): 1.0s , <1K
不公開 測資點#9 (2%): 1.0s , <1K
不公開 測資點#10 (2%): 1.0s , <1K
不公開 測資點#11 (2%): 1.0s , <1K
不公開 測資點#12 (2%): 1.0s , <1K
不公開 測資點#13 (2%): 1.0s , <1K
不公開 測資點#14 (2%): 1.0s , <1K
不公開 測資點#15 (2%): 1.0s , <1M
不公開 測資點#16 (2%): 1.0s , <1M
不公開 測資點#17 (2%): 1.0s , <1M
不公開 測資點#18 (2%): 1.0s , <1M
不公開 測資點#19 (2%): 1.0s , <1M
不公開 測資點#20 (2%): 1.0s , <1M
不公開 測資點#21 (2%): 1.0s , <1M
不公開 測資點#22 (2%): 1.0s , <1M
不公開 測資點#23 (2%): 1.0s , <1M
不公開 測資點#24 (2%): 1.0s , <1M
不公開 測資點#25 (2%): 1.0s , <1M
不公開 測資點#26 (2%): 1.0s , <1M
不公開 測資點#27 (2%): 1.0s , <1M
不公開 測資點#28 (2%): 1.0s , <1M
不公開 測資點#29 (2%): 1.0s , <1M
不公開 測資點#30 (2%): 1.0s , <1M
不公開 測資點#31 (2%): 1.0s , <10M
不公開 測資點#32 (2%): 1.0s , <10M
不公開 測資點#33 (2%): 1.0s , <1M
不公開 測資點#34 (2%): 1.0s , <10M
不公開 測資點#35 (2%): 1.0s , <10M
不公開 測資點#36 (2%): 1.0s , <10M
不公開 測資點#37 (2%): 1.0s , <10M
不公開 測資點#38 (2%): 1.0s , <10M
不公開 測資點#39 (2%): 1.0s , <10M
不公開 測資點#40 (2%): 1.0s , <1M
不公開 測資點#41 (2%): 1.0s , <1M
不公開 測資點#42 (2%): 1.0s , <1M
不公開 測資點#43 (2%): 1.0s , <10M
不公開 測資點#44 (2%): 1.0s , <10M
不公開 測資點#45 (2%): 1.0s , <10M
不公開 測資點#46 (2%): 1.0s , <10M
不公開 測資點#47 (2%): 1.0s , <10M
不公開 測資點#48 (2%): 1.0s , <1K
不公開 測資點#49 (2%): 1.0s , <1K
提示 :
標籤:
出處:
4th CPSC [編輯:
cpsc_organizer (CPSC主辦人)
]


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