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

Problem Statistics

Solved Member: 31　　Submission: 188　　User Tried: 39

Statement:

梓喵又回來買醬油了！！
自從上一次，梓喵去買醬油之後，你已經被她的醬油瓶壓垮而得到幸福了。(如果你已經AC過這題的話...)

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

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

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

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

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

告訴我們梓喵要花費多少精力吧！

Input:Output:

輸入的第一行有一個整數n (1≤n≤100000)，代表商店街有幾間商店。
第二行有n個正整數，依序代表編號1至編號n的商店所賣的醬油價格。

你可以假設所有醬油價格都可以用INT儲存。

一個正整數，代表梓喵要花費的精力。

Sample Input:Sample Output:

5
1 5 2 4 3

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

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

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