P7137 [THUPC2021 初赛] 切切糕（博弈 概率）

P7137 [THUPC2021 初赛] 切切糕

-> 双倍经验：Game on Sum (Hard Version)

有 n" role="presentation" style="position: relative;">n$n$ 块方蛋糕，绝顶聪明的 Sight 和 Sirrel 决定将每块蛋糕都分成两块各自品尝。Sight 会依次将每块蛋糕分成两块，而 Sirrel 有 m" role="presentation" style="position: relative;">m$m$ 次优先选择权。

对于 n" role="presentation" style="position: relative;">n$n$ 轮操作，每一次 Sight 会先选择一块蛋糕，将它随意分成任意大小分配的两块(可以是实数)；如果 Sirrel 还有剩余的优先选择权，她可以选择一块，否则由 Sight 优先选择。

最终两人都希望自己得到的蛋糕总量最大，求 Sight 能得到的最大蛋糕总和。

n≤2500,Ai≤5×104" role="presentation" style="position: relative;">n≤2500,Ai≤5×104$n\le 2500,A_i\le 5\times {10}^4$。

由于优先选择权在 Sirrel 手里，我们不妨以她作为主视角考虑问题。而且如果以 Sight 的视角来看，直接由方程解出的 x" role="presentation" style="position: relative;">x$x$ 可能会大于 Ai" role="presentation" style="position: relative;">Ai$A_i$ 不合法，而 Sirrel 直接不适用优先权即可。

★Important" role="presentation" style="position: relative;">★Important$★\mathtt{\text{Important}}$：一般博弈论的 DP 题都是从后往前 DP，即从确定的终止状态向初始状态 DP，因为绝顶聪明这一条件使得双方都能预测到他们当前的行为对后续局面的影响，可以说只有后效性而没有前效性。若 i,j" role="presentation" style="position: relative;">i,j$i,j$ 确定，则两人之前的决策对当前决策无影响。

因此，设 fi,j" role="presentation" style="position: relative;">fi,j$f_{i,j}$ 表示已经分完了 i" role="presentation" style="position: relative;">i$i$ 块蛋糕，Sirrel 使用了 j" role="presentation" style="position: relative;">j$j$ 次选择权的最大收益，设这一次切出的蛋糕大小为 x>Ai−x" role="presentation" style="position: relative;">x>Ai−x$x>A_i-x$，分两类讨论：

• 如果使用了一次选择权，收益为 fi−1,j−1+x" role="presentation" style="position: relative;">fi−1,j−1+x$f_{i-1,j-1}+x$；
• 如果没有使用，收益为 fi−1,j+Ai−x" role="presentation" style="position: relative;">fi−1,j+Ai−x$f_{i-1,j}+A_i-x$。

那么综合收益为 min{fi−1,j−1+x,fi−1,j+Ai−x}" role="presentation" style="position: relative;">min{fi−1,j−1+x,fi−1,j+Ai−x}$min\{f_{i-1,j-1}+x,f_{i-1,j}+A_i-x\}$。

那么如果可爱邪恶的 Sight 要让她尽可能收益少，就需要让两者相等。则收益为 fi−1,j−1+fi−1,j+Ai2" role="presentation" style="position: relative;">fi−1,j−1+fi−1,j+Ai2${\displaystyle \frac{f_{i-1,j-1}+f_{i-1,j}+A_i}{2}}$。

直接 DP 就行啦！。。？真的吗？

发现可爱邪恶的 Sight 会先切大小较小的蛋糕，这会让爱可爱的 Sirrel 更加为难。先排序。

#define Maxn 2505
int n,m;
double a[Maxn],sum[Maxn],f[Maxn][Maxn];
bool cmp(double x,double y){ return x>y; }
int main()
{
	n=rd(),m=rd();
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)
	{
		f[i][0]=0,f[i][i]=sum[i]/2.0;
		for(int j=1;jfmax((f[i-1][j]+f[i-1][j-1]+a[i])/2.0,f[i-1][j]);
	}
	printf("%.6lf\n",sum[n]-f[n][m]);
	return 0;
}