题解 P7137 【[THUPC2021 初赛]切切糕】

decoqwq · 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]);
}