問題概要
Osuと呼ばれるゲームをする。連続するx個の○についてx2の得点が与えられる。
n文字の文字列が与えられるので、得点の期待値を求める。ただし、i番目の文字が○である確率はpiである。
方針
n2 = 2 * nC2 + n
という関係から以下のような問題の読み替えができる。「連続する○について○の長さの2乗が加点される。」→ 「一つの○につき1点加点し、○のペアについて間に×が一つもなければ2点加点する。」
これを利用して期待値を計算する。後半のペアうんぬんのところは動的計画を使って計算する。
ソースコード
using namespace std; #define REP(i,n) for(int i=0; i<(int)(n); i++) #define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++) #define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++) int main() { int n; static double p[100000]; cin >> n; REP(i, n) scanf("%lf", p+i); double ret = 0; double q = 0; REP (i, n) { ret += p[i]; if (i > 0) q = (q + p[i-1]) * p[i]; ret += 2*q; } printf("%.8lf\n", ret); return 0; }
0 件のコメント:
コメントを投稿