20938번 - 반짝반짝 스페셜 저지

이제 조금밖에 남지 않은 겨울 기분을 만끽하고 싶은 수현이는 지금부터라도 크리스마스 트리를 장식하려고 한다.

크리스마스 트리는 전구 스트립으로 두른다. 전구 스트립에는 전구 $N$개가 일(一)자로 설치되어 있고, 왼쪽에 전원을 넣는다. 특이하게도 이 전구 스트립은 전구 하나가 고장 나면 고장 난 전구를 시작으로 오른쪽에 설치되어 있는 모든 전구에 불이 들어오지 않게 된다.

수현이는 반짝반짝한 걸 좋아한다. 따라서 전구 스트립을 최대 $K$개의 토막으로 자르고, 왼쪽에 전원을 각각 다시 넣어서 트리를 장식할 것이다. 이렇게 해서 불이 들어온 전구의 개수의 기댓값이 최대가 되게 하고 싶다. 각각의 전구가 고장 날 확률이 주어질 때 불이 들어온 전구의 개수의 기댓값의 최댓값을 계산하라.

다음과 같이 입력이 주어진다.

불이 들어온 전구의 개수의 기댓값의 최댓값을 출력한다.

출력한 값과 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하여야 한다.

• $N$은 전구 스트립의 길이이다. ($1 \leq N \leq 2\,500$)
• $1 \leq K \leq \min \left\{ N, 10 \right\}$
• $p_i$는 전구가 고장 날 확률이며, 소수점 아래 두 자리까지 주어진다. 왼쪽 전구에서 오른쪽 전구의 순서로 주어진다. ($0 \leq p_i \leq 1$)
• $N$과 $K$는 정수다.