你这个是在吹牛皮啊
pomelo_nene
2022-01-23 16:04:28
最近成功成为 Motivation 魔怔人……随便写点。
有一个可能太简单导致不好发现的结论，当前状态如果选择了随机抽，那么会随机抽直到抽到一个。
根据 WC2022 讲的 canonicalize（决策规范化），我们考虑将两个操作分开执行（可以用同样出处的 exchange argument 证明，交替执行的策略不会更优）。那么在先执行随机抽和先买中显然先随机抽更优秀（毕竟一开始抽中的概率会大一些，这是个直观的东西）。
然后是，我们要找到一个时间点，使得在之前我们选择随机抽，在之后直接买。定义 $f_i$ 为选择了 $i$ 个东西之后，再买一个随机的东西的期望花费。抽中没抽到的东西的概率是 $\dfrac{n-i}{n}$，那么期望抽 $\dfrac{n}{n-i}$ 次。那么 $f_i = \dfrac{x}{2}\left( \dfrac{n}{n-i} -1 \right) + x$。
注意到随机抽去买这个动作得到的东西我根本不知道，也无法操控。将随机抽归纳到直接买是不可行的。
Motivation: 将直接买这个操作，通过先随机抽再直接买这个性质，变成跟随机抽一个性质。
记没买的东西的总价值为 $c$，还有 $p$ 个没选。注意到在两个操作都是通过固定花费随机购买一个东西，那么每种购买顺序概率相同，当前如果直接买相当于期望花费 $\dfrac{c}{p}$ 买一个随机的还没有的东西。
那么在确定了 $c,p$ 的情况下，我们的最优决策固定，花费为 $\min\left(f_{n-p},\dfrac{c}{p}\right)$。
观察数据范围，猜测需要 $O(n^2 \sum c_i)$ 的算法。因此我们可以求出选了 $p$ 个东西总价格为 $c$ 的方案数。
因为每种购买顺序概率已经相同了，可以求出 $dp_{p,c}$ 表示选了 $p$ 个东西总价格为 $c$ 的概率，相当于方案数再除以 $\dbinom{n}{p}$。
那么最优的答案是 $\displaystyle \sum_{i=0}^{n-1} C(i)$，其中 $C(i)$ 表示在选择了 $i$ 个东西之后再选择一个东西的最优期望花费。
显然 $C(i)$ 也是个求和的形式。令 $s = \sum c_i$，枚举剩下的东西的总价格 $c$，那么 $\displaystyle C(i) = \sum dp_{i,c} \cdot \min\left(f_i,\dfrac{s-c}{n-i}\right)$。
```cpp
/*
他决定要“格”院子里的竹子。于是他搬了一条凳子坐在院子里，面对着竹子硬想了七天，结果因为头痛而宣告失败。
DONT NEVER AROUND . //
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double DB;
DB fac[105];
DB C(int n,int m){return (n<m || m<0)?0:fac[n]/fac[m]/fac[n-m];}
int n,x,a[10005],sum;
DB f[10005],dp[105][10005];
DB getMin(int c,int p){return min(DB(sum-c)/DB(n-p),f[p]);}
int main(){
scanf("%d %d",&n,&x);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
for(int i=0;i<n;++i) f[i]=DB(x)/DB(2)*(DB(n)/DB(n-i)+1);
fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=fac[i-1]*DB(i);
dp[0][0]=1;
for(int i=1;i<=n;++i) for(int j=i;j;--j) for(int k=sum;k>=a[i];--k) dp[j][k]+=dp[j-1][k-a[i]];
for(int i=0;i<=n;++i) for(int j=0;j<=sum;++j) dp[i][j]/=C(n,i);
DB ans=0;
for(int i=0;i<n;++i) for(int j=0;j<=sum;++j) ans+=dp[i][j]*getMin(j,i);
printf("%.10Lf",ans);
return 0;
}
```