P5308 [COCI2019] Quiz 题解

· · 题解 

看了看题解里好像没有一篇 DP 正推的，那不妨我来写一篇吧~

Solution：

设 f[i][j] 表示前 i 名参赛者中挑战 j 轮所获得的奖最大值，

易得状态转移方程 :

f[i][k]=\max\limits_{0 \leq j < i}(f[j][k-1]+ \frac{i-j}{n-j})

考虑斜率优化，既得：

f[j][k-1]-\frac{j}{n-j}=(-i)\times \frac{1}{n-j}+f[i][k]

令 f[j][k-1] 为 y，\frac{1}{n-j} 为 x，(-i) 为 k，f[i][k] 为 b。

其中 x、k 均满足单调性，则可用单调队列维护上凸包进行斜率优化 DP。

然后看看数据范围，O(nk) 的时间复杂度直接 GG，考虑优化，简单证明 (口胡 ，反正也没学过别的优化方式) 便知是 WQS 二分，然后注意各种细节就行了。 (￣▽￣)~*

Code:

#include<bits/stdc++.h>
#define inl inline
#define re register
typedef long double ld;
using namespace std;
const int maxn=100005,inf=1e9;
const double eps=1e-14;
inl int Read()
{
    re int s=0,f=1;
    re char c;
    while(!isdigit(c=getchar()))
        if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) s=s*10+c-'0';
    return s*f;
}
int n,K,head,tail,q[maxn],g[maxn];
ld f[maxn];
inl ld X(int x)
{
    return 1.0/(n-x);
}
inl ld Y(int x)
{
    return f[x]-1.0*x/(n-x);
}
inl ld Calc(int x,int y)    //为了避免精度误差最好用叉积，只是我懒得~
{
    return (Y(y)-Y(x))/(X(y)-X(x));
}
inl bool Check(double x)
{
    head=tail=1;
    for(re int i=1;i<=n;++i)
    {
        while(head<tail&&Calc(q[head],q[head+1])>=-1.0*i) ++head;
        f[i]=Y(q[head])+i*X(q[head])-x;    //由于是求最大值，应减去额外贡献才能让分段越多代价越大 
        g[i]=g[q[head]]+1;
        while(head<tail&&Calc(q[tail-1],q[tail])<=Calc(q[tail],i)) --tail;
        q[++tail]=i;
    }
    return g[n]>=K;
}
int main()
{
    n=Read();
    K=Read();
    double l=0.0,r=1.0*inf;    //因为 f 可取实数，所以二分的额外贡献也要取到实数 
    while(r-l>=eps)
    {
        re double mid=(l+r)*0.5;
        if(Check(mid)) l=mid;
        else r=mid;
    }
    Check(l);
    printf("%.9Lf\n",f[n]+1.0*l*K);
    return 0;
}