题解：CF1267G Game Relics

· · 题解

题目大意

共有 n 个圣物，购买第 i 个圣物需要 c_i 个碎片，但你也可以花费 x 个碎片随机获得一个圣物，如果你曾经获得过这个圣物，将会返还你 x\div 2 个碎片。

需要求出购买所有圣物所需的最小期望碎片数量。

思路

容易发现，最优策略是先随机购买，再买下剩下的圣物。

设当前有 i 个圣物，设当前拥有的圣物总价值为 j，所有圣物的总价值为 tot。

每次通过随机的方式获得一个新圣物的概率为 \frac{n-i}{n}。期望花费为 (\frac{n}{n-i}+1)*\frac{n}{2}，加一是因为最后随到新的不会返还碎片。

每次通过直接购买一个圣物的期望花费为 \frac{tot-j}{n-i}。

知道了这些，我们要如何算出答案呢？

考虑到直接设计期望 dp 有点难，所以设 dp_{i,j} 表示当前有 i 个圣物，拥有的圣物总价值为 j 时，转移到下一个状态的期望花费，dp_{i,j} 的值即为前面两种情况的最小值。

再设 p_{i,j} 表示在 n 个圣物中随机选 i 个，拥有的圣物总价值为 j 的概率，可以用出现次数除以总方案数来计算。

那么答案就是 \sum dp_{i,j}\times p_{i,j}。

代码

#include<bits/stdc++.h>
using namespace std;
int n,x,a[114],tot;
double p[114][11451],dp[114][11451],ans,c[114][114];
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
int main(){
    n=read();x=read();
    for(int i=1;i<=n;i++)a[i]=read();
    c[0][0]=1;
    for(int i=1;i<=n;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    p[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=i-1;~j;j--)for(int k=tot;~k;k--)p[j+1][k+a[i]]+=p[j][k];
        tot+=a[i];
    }
    for(int i=0;i<n;i++)for(int j=0;j<=tot;j++)p[i][j]/=c[n][i];
    for(int i=0;i<n;i++)for(int j=0;j<=tot;j++)dp[i][j]=min(1.0*(tot-j)/(n-i),(1.0*n/(n-i)+1)*x/2);
    for(int i=0;i<n;i++)for(int j=0;j<=tot;j++)ans+=dp[i][j]*p[i][j];
    printf("%.17lf",ans);
    return 0;
}