2001 . 闖關遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

79.2% (19/24)

Submission's AC Ratio

22.0% (86/391)

Tags

CKcon 2018-CKcon-sup DP-optimization DP

Description

盩僰麌最近迷上了叫作ニュー・スーパーフックガール的遊戲，但是他常常對他的成績不太滿意，於是他決定採取一種策略來練習這個遊戲裡的每個關卡。

這個遊戲一共有N個關卡，由0編號到N−1。每一關盩僰麌需要1單位的時間去練習以獲得他想要的成績。他認為分段練習是最好的方法，於是他把這些關卡分成k個階段，使得每一段裡的關卡的編號都連續。

盩僰麌對分段練習有特殊的堅持，他並不只是單純的把每個關卡都刷過一次而已。盩僰麌寫了一個程式，協助他挑選接下來要練習哪一關。
對於每個階段，當這個階段中每一個關卡都練習完了之後，盩僰麌就會練習下一個階段，重複直到每個階段的每個關卡都練習完畢。

而盩僰麌寫的程式的運作方式如下：假設盩僰麌現在練習的階段中，盩僰麌已經練習過的關卡編號是a1,a2,...,ax，而還沒練習過且編號最低的關卡編號是b，則這個程式會計算出C=tb+ta1+ta2+⋯+taX，然後隨機決定它的輸出：tbC的機率會輸出編號b的關卡、ta1C的機率會輸出編號a1的關卡，以此類推。

不過因為不久後就要舉行這個遊戲的比賽了，請幫盩僰麌算出，如果按照他的這個練習方法，對於每種階段的劃分方法，練習完這個遊戲的期望時間最短可以到多少。

Input Format

第一行有兩個正整數N,k，代表的意義如題敘所示。
第二行有N個正整數，第i個數字代表ti。

對於所有的測資，k≤N，ti≤200000。

Output Format

請輸出一個數字，代表完成所有關卡所需的最少期望時間。
只要輸出的答案與正確答案的絕對誤差或相對誤差不超過10−4（即|output−ans|max(1,ans)≤10−4），那麼將會視為正確。

Sample Input 1

4 2
100 3 5 7

Sample Output 1

5.7428571429

Hints

範例測資中，其中一種最好的策略是將第1關分為一段，第2~4關分為第二段，第一段的期望時間為1單位時間，第二段的期望時間為4.7428571429單位時間，總共為5.7428571429，並且沒有別的分段方式能取得更短的總期望時間。

2018/03/20 測資加強。

Problem Source

建國中學106學年度校隊補選pB

Subtasks

No. Testdata Range Constraints Score
1 0~11 N≤500,k≤3 8
2 0~28 N≤1000,k≤5 14
3 0~39, 41 N≤1000,k≤1000 32
4 40, 42~54 N≤200000,k≤50 56
5 0~72 N≤200000,k≤200000 90

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1900 131072 262144 1 2 3 5
1 1900 131072 262144 1 2 3 5
2 1900 131072 262144 1 2 3 5
3 1900 131072 262144 1 2 3 5
4 1900 131072 262144 1 2 3 5
5 1900 131072 262144 1 2 3 5
6 1900 131072 262144 1 2 3 5
7 1900 131072 262144 1 2 3 5
8 1900 131072 262144 1 2 3 5
9 1900 131072 262144 1 2 3 5
10 1900 131072 262144 1 2 3 5
11 1900 131072 262144 1 2 3 5
12 1900 131072 262144 2 3 5
13 1900 131072 262144 2 3 5
14 1900 131072 262144 2 3 5
15 1900 131072 262144 2 3 5
16 1900 131072 262144 2 3 5
17 1900 131072 262144 2 3 5
18 1900 131072 262144 2 3 5
19 1900 131072 262144 2 3 5
20 1900 131072 262144 2 3 5
21 1900 131072 262144 2 3 5
22 1900 131072 262144 2 3 5
23 1900 131072 262144 2 3 5
24 1900 131072 262144 2 3 5
25 1900 131072 262144 2 3 5
26 1900 131072 262144 2 3 5
27 1900 131072 262144 2 3 5
28 1900 131072 262144 2 3 5
29 1900 131072 262144 3 5
30 1900 131072 262144 3 5
31 1900 131072 262144 3 5
32 1900 131072 262144 3 5
33 1900 131072 262144 3 5
34 1900 131072 262144 3 5
35 1900 131072 262144 3 5
36 1900 131072 262144 3 5
37 1900 131072 262144 3 5
38 1900 131072 262144 3 5
39 1900 131072 262144 3 5
40 1900 131072 262144 4 5
41 1900 131072 262144 3 5
42 1900 131072 262144 4 5
43 1900 131072 262144 4 5
44 1900 131072 262144 4 5
45 1900 131072 262144 4 5
46 1900 131072 262144 4 5
47 1900 131072 262144 4 5
48 1900 131072 262144 4 5
49 1900 131072 262144 4 5
50 1900 131072 262144 4 5
51 1900 131072 262144 4 5
52 1900 131072 262144 4 5
53 1900 131072 262144 4 5
54 1900 131072 262144 4 5
55 1900 131072 262144 5
56 1900 131072 262144 5
57 1900 131072 262144 5
58 1900 131072 262144 5
59 1900 131072 262144 5
60 1900 131072 262144 5
61 1900 131072 262144 5
62 1900 131072 262144 5
63 1900 131072 262144 5
64 1900 131072 262144 5
65 1900 131072 262144 5
66 1900 131072 262144 5
67 1900 131072 262144 5
68 1900 131072 262144 5
69 1900 131072 262144 5
70 1900 131072 262144 5
71 1900 131072 262144 5
72 1900 131072 262144 5
Submit
Back to Top