Luogu P1654 OSU!

2024-08-21 14:34:51

写法和CF235B Let's Play Osu!非常相似。但是这个题厉害就厉害在统计的贡献里面有一个平方的期望，而这个平方的期望和期望的平方是完全不一样的，需要另外统计，逻辑上仔细想一想就会明白。

期望\(dp\)没那么可怕，但是确实非常不容易调试。所以一定要在第一次推出式子的时候，保证式子的正确。哪怕先写一个暴力，也比写出锅过不了样例根本没法调的正解要好。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n; double p[N], E1[N], E2[N], ans;

int main () {

	cin >> n;

	for (int i = 1; i <= n; ++i) {

		cin >> p[i];

		E1[i] = p[i] * (E1[i - 1] + 1);

		E2[i] = p[i] * (E2[i - 1] + 2 * E1[i - 1] + 1);

		ans += p[i] * (3 * E2[i - 1] + 3 * E1[i - 1] + 1);

	}

	printf ("%.1lf\n", ans);

}

最新文章

热门文章