description
你在玩抽卡游戏，想抽中所有 (n) 个角色。你有两种选择：
（1）花费 (c_i) 直接购买第 (i) 个角色。
（2）花费 (x) 随机从 (n) 个角色中抽取一个。如果重复了则返还 (frac{x}{2})。
求最优策略下的最小期望氪金量。
solution
如果还剩下 (k) 个，随机抽中一个的期望花费为 (frac{n+k}{2k}x)。
最优策略下，选择购买后不会再抽卡。不会证，不过盲猜归纳法可以证，反正很好理解。
因此可以对问题做等价转化，将原先的 “钦定一个购买” 变成 “随机从没有的选择一个购买”（反正接下来肯定要一直买下去）。
转化的好处是：到达每个子集 (S) 的概率为 (frac{1}{inom{n}{|S|}})，与子集具体是啥无关。
再做等价转化：在 (S) 中直接购买的代价为 (frac{sum_{iin S}c_i}{|S|})，即代价的平均数。
转化的好处是：(S) 对应的最优决策代价为 (min{frac{n+|S|}{2|S|}x,frac{sum_{iin S}c_i}{|S|}})，与 (|S|) 长啥样彻底无关。
可以证明这样转化不会让 (S) 对应的最优策略变化（这个的确可以归纳法证），也不会让总代价变化。
然后背包一下即可。时间复杂度 (O(n^2sum c))。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int c[105], n, x;
double f[105][MAXN + 5];
int main() {
scanf("%d%d", &n, &x); for(int i=1;i<=n;i++) scanf("%d", &c[i]);
int s = 0; f[0][0] = 1;
for(int i=1;i<=n;s+=c[i],i++) {
for(int j=s;j>=0;j--)
for(int k=i-1;k>=0;k--)
f[k + 1][j + c[i]] += f[k][j]*(k + 1)/(n - k);
}
double ans = 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=s;j++)
ans += f[i][j]*min(1.0*(n+i)/(2*i)*x, 1.0*j/i);
printf("%.9f
", ans);
}
details
可以从 “这个算法应该长啥样才能过” 反向思考，怎么才能把指数级复杂度降成多项式复杂度，
然后就想到可以尝试用集合 S 的和/大小等价替代这个集合。
有贪心结论证不出来没关系，比较显然就直接用试试。
说了这么多，我还是不会做。