CF1267G Game Relics

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$的概率

并不好算，可以考虑算方案数，然后再$/\left(\genfrac{}{}{0ex}{}{n}{i}\right)$

然后枚举所有的情况，用权值 * 概率求个和即可

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;
}