2001 . 闖關遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

81.8% (18/22)

Submission's AC Ratio

21.6% (80/371)

Tags

CKcon 2018-CKcon-sup DP-optimization DP

Description

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

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

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

而盩僰麌寫的程式的運作方式如下：假設盩僰麌現在練習的階段中，盩僰麌已經練習過的關卡編號是$a_1,a_2,...,a_x$，而還沒練習過且編號最低的關卡編號是$b$，則這個程式會計算出$C=t_b+t_{a_1}+t_{a_2}+\cdots+t_{a_X}$，然後隨機決定它的輸出：$\frac{t_b}{C}$的機率會輸出編號$b$的關卡、$\frac{t_{a_1}}{C}$的機率會輸出編號$a_1$的關卡，以此類推。

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

Input Format

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

對於所有的測資，$k \leq N$，$t_{i} \leq 200000$。

Output Format

請輸出一個數字，代表完成所有關卡所需的最少期望時間。
只要輸出的答案與正確答案的絕對誤差或相對誤差不超過$10^ {-4}$（即$\frac{|output-ans|}{max(1,ans)}\leq 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 \leq 500, k \leq 3$ 8
2 0~28 $N \leq 1000, k \leq 5$ 14
3 0~39, 41 $N \leq 1000, k \leq 1000$ 32
4 40, 42~54 $N \leq 200000, k \leq 50$ 56
5 0~72 $N \leq 200000, k \leq 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