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：

Problem Setter

bigelephant29

Testdata：

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9-1	1000ms	65536kb	10
9-2	1000ms	65536kb
10	1000ms	65536kb	10

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。

沒有留言:

張貼留言

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

注意：只有此網誌的成員可以留言。

2016年2月24日 星期三

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

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

沒有留言:

張貼留言

2016年2月24日星期三

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

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