奶龙题,主要是凸性的证明,然后 wqs 二分求解即可。
轮数的选择是 \(1\) ~ \(n\),假如是 \(1\) 轮,答案显然为 \(1\),为 \(n\) 轮,答案就是 \(\sum_{i=1}^{n}i^{-1}\),从这里就可以直接猜出凸性了。
然后是不考虑轮数限制的求法,直接 dp 即可:\(f_{i}=\max\{f_j+\frac{i-j}{i}\}\),再减去个二分的 \(mid\)。
式子显然能够斜率优化,这个题就做完了。
注意精度,保险起见开long double
。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define ld long double
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
const int N=1e5+10;
const ld eps=1e-12;
int n,k,g[N],q[N];ld f[N];
ld Y(int a){return f[a];}
ld X(int a){return (ld)a;}
ld slope(int a,int b){return (ld)(Y(a)-Y(b))/(X(a)-X(b));}
int calc(ld mid){
int hh=1,tt=1;q[1]=0;
memset(g,0,sizeof(g));
FOR(i,1,n){
while(hh<tt&&slope(q[hh],q[hh+1])-1.0/i>eps) hh++;
f[i]=f[q[hh]]+(ld)(i-q[hh])/i-mid;
g[i]=g[q[hh]]+1;
while(hh<tt&&slope(q[tt],q[tt-1])-slope(q[tt],i)<eps) tt--;
q[++tt]=i;
}
return g[n];
}
int main(){
n=rd,k=rd;
ld l=0,r=10000000;
while(r-l>eps){
ld mid=(l+r)/2.0;
if(calc(mid)>=k) l=mid;
else r=mid;
}
calc(l);
double ans=f[n]+l*k;
printf("%.9lf\n",ans);
return 0;
}
标签:ch,int,mid,long,P5308,hh,Akvizna,2019,define
From: https://www.cnblogs.com/summ1t/p/18528086