[CF 146 B] Let's Play Osu!

m^2 = m+m+m+...+m (총 m개)  이므로

m 개의 O가 연속되어 있을 때, 한번에 m^2을 획득한 게 아니라

m 번의 클릭(O) 이 각각 m 점을 획득한 것이라고 바꿔 생각할 수 있다.

이러면, 정답 = ∑ ( i 번째 클릭이 얻은 점수의 기댓값) = ∑ ( i 번째 클릭이 속한 O 그룹의 길이의 기댓값) 이 된다.

이제 쉽게 DP를 설정해보면,

DP[i] = i 번째가 클릭이 속한 O 그룹의 길이의 기댓값.

그런데 이 DP[i] 를 구하려고 해보면

(i-1) 번째 클릭의 성공률이 DP[i] 에 영항을 끼치고,  i 번째 클릭의 성공률이 DP[i-1]에 영향을 끼쳐서

결국 상호 간에 영향을 끼치기 때문에 까다로워짐을 알 수 있다.

DP[i] 의 부분 문제로 DP[i-1]을 설정해놓고, DP[i-1]의 부분 문제로 그 상위 문제인 DP[i]를 설정하긴 힘들기 때문이다.

이를 해소하기 위해서 DP[i]를 분해하면,

left[i] = i 번째가 클릭이 속한 O 그룹 중 'i의 오른쪽' 길이의 기댓값.

right[i] = i 번째가 클릭이 속한 O 그룹 중 'i의 왼쪽' 길이의 기댓값.

이와 같이 설정할 수 있다.

left[i] 의 부분 문제로는 left[i-1], right[i] 의 부분 문제로는 right[i+1] 로 루프 없이 부분 문제를 설정할 수 있다.

left[i] 와 left[i-1]의 관계는 수학적으로 간단.

// code by RiKang, weeklyps.com
#include<stdio.h>
 
const int N = 100000;
int n;
double a[N+5];
double left[N+5];
double right[N+5];
double ans;
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf",&a[i]);
    a[0]=a[n+1]=0;
    for(int i=1;i<=n;i++)
        left[i]=(left[i-1]+1)*a[i];
    for(int i=n;i>=1;i--)
        right[i]=(right[i+1]+1)*a[i];
    for(int i=1;i<=n;i++)
        ans+=a[i]*(1+left[i-1]+right[i+1]);
    printf("%.9lf",ans);
    return 0;
}