题目链接 裸的( ext{wqs})二分(+)斜率优化
二维( ext{dp})的式子长这样：(f[i][j]=max{f[k][j-1]+frac{i-k}{i}})，答案就是(f[n][k])。
考虑( ext{wqs})二分去掉(k)这一维，然后式子变成了(f[i]=max{f[j]+frac{i-j}{i}-val})，可以斜率优化了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,k,q[maxn],num[maxn];
double inv[maxn],f[maxn];
inline void calc(double val){
int l,r;q[l=r=1]=0;
for(int i=1;i<=n;i++){
while(l<r&&q[l+1]-q[l]<=i*(f[q[l+1]]-f[q[l]]))l++;
f[i]=f[q[l]]+1-q[l]*inv[i]-val;num[i]=num[q[l]]+1;
while(l<r&&(f[q[r]]-f[i])*(q[r]-q[r-1])<=(f[q[r-1]]-f[q[r]])*(i-q[r]))r--;
q[++r]=i;
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)inv[i]=1.0/i;
double l=0,r=100,mid;
for(int i=1;i<=50;i++){
mid=(l+r)/2;
calc(mid);
if(num[n]>k)l=mid;
else r=mid;
}
calc(l);
printf("%.9lf
",f[n]+k*l);
return 0;
}