洛谷 5308 [COCI2019] Quiz 题解

题意简述

有 $n$ 个人，$k$ 轮比赛。每次如果淘汰了 $x$ 个人，还剩下 $m$ 个人，得分增加 $\dfrac{x}{m}$ 的奖金。。假设你能控制每次淘汰多少人，最大化得分。

思路

设 $dp[i]$ 表示现在还剩下 $i$ 个人的最优方案 （先不考虑轮数）。

那么 $dp[i]=max(dp[j]+\dfrac{i-j}{i})$，其中 $0\le j<i$

显然能斜率优化。

觉得不显然的小伙伴们看一下：

斜率优化式子：
若 $j\ge k$ 且 $j$ 优于 $k$，那么
$dp[j]+\dfrac{i-j}{i}>dp[k]+\dfrac{i-k}{i}$
$dp[j]-\dfrac{j}{i}>dp[k]-\dfrac{k}{i}$
$dp[j]-dp[k]>\dfrac{j-k}{i}$
由于 $j\ge k$，所以 $j-k>0$，直接除
$\dfrac{dp[j]-dp[k]}{j-k}>\dfrac{1}{i}$

也就是 $slope(k,j)>\dfrac{1}{i}$ 时，$k$ 就没用了。

而如果每一个时刻 $k$ 没用了，后面 $i$ 更大，$\dfrac{1}{i}$ 更小，$k$ 更不可能有用。这个是弹队首的条件。

其次可以看出来，这个队列是斜率单调递减的。这个就是加入队尾的条件。

然后我们就发现一个问题：$k$ 的限制怎么办？

上 $wqs$ 二分： 对于每个转移过来的 $j$，我们给他加上一个附加权值 $x$。显然，$x$ 加的越多，选的段数越少。转移的时候记录一下段数，二分即可。

最后的答案是 $ans-x\times k$，一定要记住了，是 $k$。

代码

复制

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define EPS 1e-12
    #define real long double
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    int n,k;
    void Input()
    {
        Rd(2,&n,&k);
    }
    real dp[N]; int cnt[N];
    real slope(int x,int y){return (dp[x]-dp[y])/(1.0*x-1.0*y);}
    int Q[N];
    bool cxk(real mid)
    {
        int head=1,tail=1; Q[1]=0;
        F(i,1,n)
        {
            while(head+1<=tail and slope(Q[head+1],Q[head])-1.0/i>EPS) ++head;
            int j=Q[head];
            dp[i]=dp[j]+(1.0*i-1.0*j)/(1.0*i)-mid; cnt[i]=cnt[j]+1;
            while(head<=tail-1 and slope(Q[tail-1],Q[tail])-slope(Q[tail],i)<-EPS) --tail;
            Q[++tail]=i;
        }
        return cnt[n]>=k;
    }
    void Soviet()
    {
        real l=0.00,r=1e6;
        F(i,1,100) 
        {
            real mid=(l+r)/2.0; 
            if (cxk(mid)) l=mid;
            else r=mid;
        }
        cxk(l);
        cout<<fixed<<setprecision(9)<<dp[n]+k*l<<endl;
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}