B.Rcomb
题目描述 :
Na老师有\(N\)张卷子排成一列，第i张卷子有其难度\(V_i\)，由于X爷的出现，Na老师需要将这些卷子合并为1张。每次Na老师以相等的概率随机选择两张相邻卷子，消耗两张卷子难度和的体力，得到一张难度为两张卷子难度和的卷子，求 Na老师需要消耗的体力期望值。
输入格式 :
第一行：一个整数\(N\)。
第二行：\(N\)个整数\(V_1、V_2、...、V_N\)。
输出格式 :
只有一行，一个小数ANS(小数点后保留5位)表示Na老师需要消耗的体力期望值。
数据范围 :
30% N<=10
60% N<=100
100% 1<=N<=5000 1<=V_i<=10000
Solution & Code :
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, a[N];
double dp[2][N];
// dp[i][j] 表示长度为i的序列排在第j位的试卷的期望被计入的次数
// dp[1][1] = 0 长度为 1 没有合并 次数为 0
template<typename T> void read(T &x) {
bool f = false; x = 0;
char ch = getchar();
while (ch<'0' || ch>'9') {if (ch == '-') f = true; ch = getchar();}
while (ch>='0' && ch<='9') x = x * 10 + ch - '0', ch = getchar();
if (f) x = -x;
}
int main() {
read(n);
for (int i = 1; i <= n; i++) read(a[i]);
// dp[0][0] = 0; dp[1][1] = 0;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j > 1) dp[i&1][j] += dp[(i-1) & 1][j-1] * (j-1) / (i-1) + 1.0 / (i-1);
//因为每相邻两试卷有相同概率被合并，所以每次合并的期望贡献次数为 1.0/(i-1)
if (j < i) dp[i&1][j] += dp[(i-1) & 1][j] * (i-j) / (i-1) + 1.0 / (i-1);
}
memset(dp[(i-1) & 1], 0, sizeof(dp[(i-1) & 1]));
}
double ans = 0;
for (int i = 1; i <= n; i++) {
ans += dp[n&1][i] * a[i];
}
cout<< fixed << setprecision(5) << ans << endl;
return 0;
}