a763: pB. Shark 的數學遊戲
Tags :
Accepted rate : 27人/31人 ( 87% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-02-07 12:07

Content

鯊魚(英文名字Shark)是一位從來不哭的男孩,有一天,他閒的發慌,發明了一個打發時間的數學遊戲。

規則是這樣的:

給兩個正整數 N , M ,代表有 N 個數字, 我們要將他們分成 M ( M <= N ) 個區塊,使計算後出來的值最小。

遊戲怎麼玩呢? 來看看下面的例子:

當 N = 5 , M = 3 , 且輸入的五個數字分別為 0.5 , 0.4 , 0.4 , 0.3 , 0.2 ,我們要將這數列切成三份,

如果我這樣切 0.5  |  0.4  0.4  |  0.3  0.2 

區段編號        1           2              3

計算方法為  區段1個數 * 區段1和 + (區段1個數+區段2個數) *區段2和 + (區段1個數+區段2個數+區段3個數) *區段3和

則計算出來的結果為 [1 * 0.5] + [(1+2) * (0.4+0.4)] + [(1+2+2)*(0.3+0.2)] = 5.4

如果我這樣切 0.5  |  0.4 |  0.4  0.3  0.2 

則計算出來的結果為 [1 * 0.5] + [(1+1) * (0.4)] + [(1+1+3)*(0.4+0.3+0.2)] = 5.8

Shark 想要知道可以玩出的最小值是多少

Input

單筆測資輸入

每一行有兩個正整數 N , M ( M <= N )

接下來有 N 個 < 1 且 >= 0 的小數,至多小數後1位

Output
輸出遊戲可玩出的最小值( 小數點後1位 )
Sample Input
5 3
0.5 0.4 0.4 0.3 0.2
Sample Output
5.4
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <1M
Hint :

保證:20% 的測資滿足 N <= 10 , M <= 5
   50% 的測資滿足 N <= 100 , M <= 10
   80% 的測資滿足 N <= 1000 , M <= 100
   100% 的測資滿足 N <= 2000 , M <= 100

註:校內賽僅需通過前五筆測資即可AC

特別感謝 stanley17112000 出題!!

2014/2/7 感謝 david942j 指出前五筆測資錯誤,已修正並重測!!

Tags:
出處:
2013成功高中校內賽 [管理者:
eddy841021 (C++?)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」