微网站制作公司,东莞做网站优化,百度域名登录,卢松松网站源码P7137 [THUPC2021 初赛] 切切糕 - 双倍经验#xff1a;Game on Sum (Hard Version) 有 \(n\) 块方蛋糕#xff0c;绝顶聪明的 Sight 和 Sirrel 决定将每块蛋糕都分成两块各自品尝。Sight 会依次将每块蛋糕分成两块#xff0c;而 Sirrel 有 \(m\) 次优先选择权。 对于 \(… P7137 [THUPC2021 初赛] 切切糕 - 双倍经验Game on Sum (Hard Version) 有 \(n\) 块方蛋糕绝顶聪明的 Sight 和 Sirrel 决定将每块蛋糕都分成两块各自品尝。Sight 会依次将每块蛋糕分成两块而 Sirrel 有 \(m\) 次优先选择权。 对于 \(n\) 轮操作每一次 Sight 会先选择一块蛋糕将它随意分成任意大小分配的两块(可以是实数)如果 Sirrel 还有剩余的优先选择权她可以选择一块否则由 Sight 优先选择。 最终两人都希望自己得到的蛋糕总量最大求 Sight 能得到的最大蛋糕总和。 \(n\le 2500,A_i\le 5\times 10^4\)。 由于优先选择权在 Sirrel 手里我们不妨以她作为主视角考虑问题。而且如果以 Sight 的视角来看直接由方程解出的 \(x\) 可能会大于 \(A_i\) 不合法而 Sirrel 直接不适用优先权即可。 \(\bigstar\texttt{Important}\)一般博弈论的 DP 题都是从后往前 DP即从确定的终止状态向初始状态 DP因为绝顶聪明这一条件使得双方都能预测到他们当前的行为对后续局面的影响可以说只有后效性而没有前效性。若 \(i, j\) 确定则两人之前的决策对当前决策无影响。 因此设 \(f_{i,j}\) 表示已经分完了 \(i\) 块蛋糕Sirrel 使用了 \(j\) 次选择权的最大收益设这一次切出的蛋糕大小为 \(xA_i-x\)分两类讨论 如果使用了一次选择权收益为 \(f_{i-1,j-1}x\)如果没有使用收益为 \(f_{i-1,j}A_i-x\)。 那么综合收益为 \(\min\{f_{i-1,j-1}x,f_{i-1,j}A_i-x\}\)。 那么如果可爱邪恶的 Sight 要让她尽可能收益少就需要让两者相等。则收益为 \(\dfrac{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 xy; }
int main()
{nrd(),mrd();for(int i1;in;i) scanf(%lf,a[i]);sort(a1,an1,cmp);for(int i1;in;i) sum[i]sum[i-1]a[i];for(int i1;in;i){f[i][0]0,f[i][i]sum[i]/2.0;for(int j1;ji;j) f[i][j]fmax((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;
}
