自动搬运

查看原文

来自洛谷，原作者为

	decoqwq **

搬运于2025-08-24 22:26:58，当前版本为作者最后更新于2020-12-23 12:12:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

直接算 Kiana 可以拿到的切糕不好算，考虑算 Tinytree 能拿到的最多的蛋糕。

令 $dp[i][j]$ 表示选了前 $i$ 个切糕，用了 $j$ 次优先选择权后 Tinytree 能拿到的最多的切糕，那么显然 $dp[i][0]=0$，$dp[i][i]=\frac{\sum_{j=1}^i a[j]}{2}$。

考虑转移，考虑当前位置为 $i$，则 Kiana 会想一种办法使得把 $a[i]$ 分成两部分 $x,y(x<y)$ 后，$\max\{x+dp[i-1][j],y+dp[i-1][j-1]\}$ 尽量小(因为 $dp[i-1][j-1]\leq dp[i-1][j]$)。

那么显然只需要让他们相等就行了，还要判断如果此时算出来的答案小于 $dp[i-1][j]$ 肯定是不对的，要和前者取个 $\max$。

感性理解一下，如果先选大的可以逼迫对面做出选择，先选小的给了他更多选择机会就会劣一些所以要先排序

复杂度 $O(nm)$

#include <bits/stdc++.h>
using namespace std;
double dp[2510][2510];
int n,m,a[50010];
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1,cmp);
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		dp[i][0]=0.0;
		for(int j=1;j<=min(i,m);j++)
		{
			if(j==i)
			{
				dp[i][j]=(1.0*sum/2);
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],(dp[i-1][j-1]+dp[i-1][j]+a[i])/2);
			}
		}
	}
	dp[n][m]=(1.0*sum-dp[n][m]);
	printf("%.6lf",dp[n][m]);
}