https://www.luogu.com.cn/problem/CF1267G
麻了,回头看的时候一下子不会算贡献了
白写了可还行
首先考虑抽卡的期望,假设已经抽了\(i\)个圣遗物出来,要出\(i+1\)个圣遗物的期望是
\(E(i)=\frac{i}{n}(E(i)+\frac{x}{2})+\frac{n-i}{n}\times(x+E(i+1))\)
\(E(i)-E(i+1)=(\frac{n}{n-i}+1)\times \frac{x}{2}\)
有个重要的性质:先抽卡后买
- 应为对于当前状态,假设最优选择是抽卡,如果抽卡啥也没有得到,那么状态不会变,继续抽
- 如果开始买了,说明\(\frac{剩下的}{n-i} < \frac{x}{2}(\frac{n}{n-i}+1)\),买了一个后,右边的期望会变大,左边的因为分母\(-1\),分子至少\(-1\),所以会变得更小, 所以会一直买
考虑dp,设\(f[i][j]\)表示得到了\(i\)个圣遗物,价格和为\(j\)的概率
并不好算,可以考虑算方案数,然后再\(/\binom{n}{i}\)
然后枚举所有的情况,用权值 * 概率求个和即可
code:
#include<bits/stdc++.h>
#define N 105
#define M 1005
#define db double
using namespace std;
db c[N][N], f[N][M];
void init(int n) {
for(int i = 0; i <= n; i ++) c[i][0] = 1;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
int n, x, a[N], m;
int main() {
scanf("%d%d", &n, &x);
init(n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
f[0][0] = 1;
for(int i = 1; i <= n; i ++) {
m += a[i];
for(int j = n; j >= 1; j --) {
for(int k = m; k >= a[i]; k --)
f[j][k] += f[j - 1][k - a[i]];
}
}
db ans = 0;
for(int i = 0; i < n; i ++) {
for(int j = 0; j <= m; j ++) {
ans += f[i][j] / c[n][i] * min((m - j) * 1.0 / (n - i), (n * 1.0 / (n - i) + 1) * (x / 2.0));
}
}
printf("%.14lf", ans);
return 0;
}