庆阳网站设计 贝壳下拉,襄阳谷城网站建设,完成网站建设成本,华为网站建设方案模板下载正题
题目链接:https://www.luogu.com.cn/problem/P7137 题目大意
有两个人#xff0c;有nnn个蛋糕#xff0c;第iii个蛋糕大小为aia_iai。
每一次第一个人可以选择一个蛋糕把它切成任意大小的两份#xff08;一份可以为空#xff09;。
然后第二个人有mmm次机会优先…正题
题目链接:https://www.luogu.com.cn/problem/P7137 题目大意
有两个人有nnn个蛋糕第iii个蛋糕大小为aia_iai。
每一次第一个人可以选择一个蛋糕把它切成任意大小的两份一份可以为空。
然后第二个人有mmm次机会优先选择一份拿走否则都是第一个人先拿。
两个人都希望自己拿走的最多。
求第一个人最终能拿走多少。
1≤m≤n≤25001\leq m\leq n\leq 25001≤m≤n≤2500 解题思路
现在看来还挺简单的一雪前耻了属于是。
因为是自定义顺序所以考虑起来比较麻烦所以我们先考虑怎么确定拿的顺序。
瞎猜感性思考一下不难发现如果我们把大的放在前面那么第一个人分的时候就分太不平均因为第二个人手里有选择权威慑但是如果我们把小的放在前面显然威慑权就到第一个人手里了。因为如果第二个交了太多次机会那么第一个人后面直接全拿所以此时第二个人不敢交这么多次机会那第一个人就可以全拿了。
所以我们直接敲定是从小到大分那么顺序固定之后就很简单了反过来推设fi,jf_{i,j}fi,j表示分到第iii时还有jjj次选择权的第一个人总和。 那么我们就有转移方程。 fi,jmax{min{fi−1,j−1ai−x,fi−1,jx}}(x∈[0,m2])f_{i,j}max\{min\{f_{i-1,j-1}a_i-x,f_{i-1,j}x\}\}(x\in[0,\frac{m}{2}])fi,jmax{min{fi−1,j−1ai−x,fi−1,jx}}(x∈[0,2m]) 考虑一下怎么确定这个xxx其实也很简单设Afi,j,Bfi,j−1Af_{i,j},Bf_{i,j-1}Afi,j,Bfi,j−1那么显然有BABABA。
如果B−A≥aiB-A\geq a_iB−A≥ai那么我们直接全拿aia_iai这样第二个人也不会用机会此时fi,jBf_{i,j}Bfi,jB。
如果B−A≤aiB-A\leq a_iB−A≤ai那么我们把aia_iai分给AAA不足BBB的那部分后剩下的平分给AAA和BBB此时fi,jBai−(B−A)2f_{i,j}B\frac{a_i-(B-A)}{2}fi,jB2ai−(B−A)。
时间复杂度O(nm)O(nm)O(nm) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2510;
int n,m;
double a[N],f[N][N];
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%lf,a[i]);sort(a1,a1n);for(int in;i1;i--){f[i][0]f[i1][0]a[i];for(int j1;jm;j){double Af[i1][j],Bf[i1][j-1];//BA xa/2 Bx Aa-xif(B-Aa[i])f[i][j]B(a[i]-BA)/2.0;else f[i][j]Aa[i];}}printf(%.6lf,f[1][m]);return 0;
}
