CF1267G 题解

· · 题解

想了想还是写吧，毕竟是一道比较神的期望 \text{dp}。

首先是一个简单的贪心思路：能抽卡的先抽卡，然后再去买。

原因显然，如果先买了卡，那么接下来抽卡就很有可能会抽到重复的卡，因此先抽卡再买卡。

如果我们已经有了 i 张卡，易得抽一张新卡概率为 \dfrac{n-i}{n}，则需要抽 \dfrac{n}{n-i} 次。

除了最后一次之外，其他的次数都可以让我们获得 \dfrac{x}{2} 的回馈，最后一次消耗 x 获得新卡，则期望消耗为：

(\frac{n}{n-i}-1) \times \frac{x}{2} + x

接着寻找抽卡与买的分界线。考虑把所有直接购买的花费均摊到每次之中。令已有的卡价值为 w_{have}，总价值为 w，则单次消耗为 \dfrac{w-w_{have}}{n-i}，转换策略判断条件为：

\frac{w-w_{have}}{n-i} < (\frac{n}{n-i}-1) \times \frac{x}{2} + x

接着假设 a_{i,j} 为选择了 i 张牌，已有价值为 j 的事件，dp_{i,j} 为其组合数量，则 a_{i,j} 发生的概率是：

\frac{dp_{i,j}}{c_{n}^{i}}

其中组合数可以预处理，dp_{i,j} 也可以通过背包预处理求出。

愉快结束。

#include<bits/stdc++.h>
using namespace std;
const int maxn=102;
const int maxm=10002; 
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-48;
        c=getchar();
    }
    return x*f;
}
int n,x;
double sum,ans;
int a[maxn];
double C[maxn][maxn],dp[maxn][maxm];
inline void init(){
    n=read();x=read();
    for(register int i=1;i<=n;++i) a[i]=read();
    C[0][0]=1;dp[0][0]=1;
    for(register int i=1;i<=n;++i){
        C[i][0]=1;
        for(register int j=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
    for(register int i=1;i<=n;++i){
        for(register int j=i-1;j>=0;--j){
            for(register int k=sum;k>=0;--k) dp[j+1][k+a[i]]+=dp[j][k];
        }
        sum+=a[i];
    }
}
int main(){
    init();
    for(register int i=0;i<=n-1;++i){
        for(register int j=0;j<=sum;++j) ans+=min((sum-j)/(n-i),x*(1.0*n/(n-i)+1)/2)*dp[i][j]/C[n][i];
    }
    printf("%.8lf",ans);
}