2016年2月24日 星期三

[HOJ 303]買醬油IV 之 商店問題 (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 303 - 買醬油IV 之 商店問題

Problem Statistics
Solved Member: 31  Submission: 188  User Tried: 39
Problem:
梓喵又回來買醬油了!!
自從上一次,梓喵去買醬油之後,你已經被她的醬油瓶壓垮而得到幸福了。(如果你已經AC過這題的話...)

這次梓喵來到了聞名全台的醬油街!

醬油街上有n間商店,從第一間到最後一間依序標記為1~n。

梓喵可以選擇在數間商店買醬油,但是要遵守幾項規則:

1.梓喵只能往前進,不能向後退,即她買醬油的順序要依照商店編號1~n。
2.梓喵很萌,但賣萌對老闆無用,在每間商店她只能買一瓶醬油。
3.每間商店醬油價格可能有所不同,但梓喵很有錢,她的錢怎麼花都花不光。
4.承3,梓喵有個怪癖,她買醬油只會越買越貴,所以當她買過價值C的醬油之後,所有價值小於等於C的醬油她都不放在眼裡。
5.梓喵很奇怪,在編號i的商店買醬油,她就要花費i單位的精力。

為了避免醬油不夠使用,梓喵必須買到最多瓶醬油。
但又為了避免梓喵太過勞累,在所有買得到最多瓶醬油的方案裡,請找出一種精力總花費最低的方案。

告訴我們梓喵要花費多少精力吧!
Input:
輸入的第一行有一個整數n (1≤n≤100000),代表商店街有幾間商店。
第二行有n個正整數,依序代表編號1至編號n的商店所賣的醬油價格。

你可以假設所有醬油價格都可以用INT儲存。
Output:
一個正整數,代表梓喵要花費的精力。
Sample Input:
5
1 5 2 4 3
Sample Output:
8
Problem Setter
bigelephant29
Testdata:
TestTimeMemoryScore
01000ms65536kb
11000ms65536kb10
21000ms65536kb10
31000ms65536kb10
41000ms65536kb10
51000ms65536kb10
61000ms65536kb10
71000ms65536kb10
81000ms65536kb10
9-11000ms65536kb10
9-21000ms65536kb
101000ms65536kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原