CFR 235 B. Let's Play Osu! ( DP, Math )

Problem - B - Codeforces

題意：
假設有個 OX 序列，每個連續段 'O' 長度若為 x，則該段貢獻為 x^2。已知序列長度，以及分別每個字符為 O 的機率，求期望貢獻和。

資料規模：
The first line contains an integer n (1 ≤ n ≤ 1e5) — the number of clicks. The second line contains n space-separated real numbers p1, p2, ..., pn (0 ≤ pi ≤ 1).
There will be at most six digits after the decimal point in the given pi.
TL: 2000 ms
ML: 256 MB

解法：
智商題。
智商不夠用。。。
只好看答案。。。。。
首先聰明的人貌似會直接達到結論：
N^2 = 2 * C( N, 2 ) + N
因此只要算有幾對 ( i, j ) 使得 [ i, j ] 為連續的 'O'，就能快速獨立算出右式第一項的貢獻總和。
dp[ i ]：以下標 i 的元素結尾時，對所有下標 j，j < i，[ j, i ] 皆為 'O' 的機率和。

時間 / 空間複雜度：
O( N )

int N;
vd P;

void init(){
  cin >> N;
  P = vd( N );
  for( int i = 0; i < N; ++i ){
    cin >> P[ i ];
  }
}

vd dp;

void preprocess(){
  dp = vd( N );
  for( int i = 1; i < N; ++i ){
    dp[ i ] = P[ i ] * ( dp[ i - 1 ] + P[ i - 1 ] );
  }
}

void solve(){
  double ans = 0.0;
  for( int i = 0; i < N; ++i ){
    ans += 2.0 * dp[ i ] + P[ i ];
  }
  cout << fixed << setprecision( 10 ) << ans << endl;
}