1639 . 尋找蘿莉第二彈
TopCoder
Tags
Description
你，身為一個蘿莉控，身邊當然會有許多蘿莉，其中恰有一個蘿莉是SS級的蘿莉。你原本不知情，直到農曆新年放鞭炮時，SS級的蘿莉因為被鞭炮嚇到而發出嬌柔的叫聲，你才發現他的存在。可惜當時你並沒有注意是哪隻蘿莉在叫，所以你為了要找出哪隻蘿莉是SS級的蘿莉而買了許多鞭炮。
為了省鞭炮，你將蘿莉們編號為$0$到$n-1$，依序從你的右邊開始往右排。每次放鞭炮時，你都可以控制音量，使得所有編號小於等於$k$的蘿莉都聽到了鞭炮聲（$0 \leq k \leq n-1$），剩下的蘿莉都沒有聽到鞭炮聲。如果SS級的蘿莉聽到了鞭炮聲，你就會聽到那個令人精神振奮的叫聲；如果沒有，你就只會聽到鞭炮聲。你的目標是使用最少的鞭炮找出SS級的蘿莉。
另外，你其實早就調查了每個蘿莉是SS級的機率，並以陣列$P[0],\cdots,P[n-1]$記錄，代表第$i$隻蘿莉是SS級的機率是$\dfrac{P[i]}{\sum_{j=0}^ {n-1}P[j]}$。請問，若你使用最佳的策略尋找SS級的蘿莉，所花費的鞭炮數的期望值$X$是多少？
覺得似曾相識嗎？我也這麼覺得。不過要是解法跟你現在想的那樣一樣，那為什麼這題滿分是破表的150呢？
Input Format
第一行有一個正整數$n\leq 800$ 代表蘿莉的數量，
接著第二行會有$n$個正整數，分別代表$P[0],\cdots,P[n-1]$，其中$P[i]\leq 10^ 9$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $P[i]=1$ | 13 |
| 2 (5~9) | $n\leq 18$ | 34 |
| 3 (10~14) | 無 | 53 |
| EXTRA (15~19) | $n \leq 4000$ | 50 |
最後一個子任務為加分題。
對於該子任務，$n \leq 800$的限制不再適用。
Output Format
為了方便，請輸出$X\times\sum_{i=0}^ {n-1}P[i] $。
Sample Input 1
2 1 1 1 1
Sample Output 1
Hints
對於範例測資的兩種解法：
一、先取$k=2$：
1. 如果聽到叫聲，就再取$k=0$：
1-1. 如果聽到叫聲，就找到了。
1-2. 如果沒有，取$k=1$就可以知道了。
2. 如果沒有，就再取$k=3$就可以知道了。
使用的鞭炮數的期望值是14/6。
二、也可以先取$k=0$：
1.如果聽到叫聲，就找到了。
2.如果沒有，就再取$k=2$：
2-1.如果聽到叫聲，就再取$k=1$就可以知道了。
2-2.如果沒有，就再取$k=3$就可以知道了。
使用的鞭炮數的期望值還是14/6。
Problem Source
Problem set / Description by Paupière
建國中學105學年度校隊選拔：複試pB
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 13 |
| 2 | 5~9 | 34 |
| 3 | 10~14 | 53 |
| 4 | 15~19 | 50 |