CF643C Levels and Regions

题面

简化题意

把 $n$ 关，划分成 $m$ 段，记 $i$ 所属段左端点为 $l_i$。第 $i$ 关卡用刚好一小时过关概率是 $\frac{a_i}{\sum_{j=l_i}^i a_j}$。求通关时打关总次数期望。

$n\leq 2\times 10^5,m\leq 50$。

题解

通过一关的时间的期望：

$\begin{aligned} E &= \frac{x}{y}\cdot 1+\frac{y-x}{y}\cdot\frac{x}{y}\cdot 2 +(\frac{y-x}{y})^2\cdot \frac{x}{y}\cdot 3 + \cdots \\ &= \frac{x}{y}[1+ 2\cdot\frac{y-x}{y} + 3\cdot(\frac{y-x}{y})^2 + 4\cdot(\frac{y-x}{y})^3 + \cdots] \\ \end{aligned}$

中括号里面是带系数的等比数列求和的形式：

$\begin{aligned} \sum_{k=2}^\infty k\cdot p^{k-1} &= \sum_{k=1}^\infty p^k+\sum_{l=1}^\infty\sum_{k=l}^\infty p^k \\ &= \frac{p}{1-p} + \sum_{l=1}^\infty \frac{p^l}{1-p} \\ &= \frac{p}{1-p} + \frac{p}{(1-p)^2} \\ &= \frac{p(2-p)}{(1-p)^2} \end{aligned}$

$p=\frac{y-x}{y}=1-\frac{x}{y}$，代入：

$\begin{aligned} E &= \frac{x}{y}[1 + 2\cdot\frac{y-x}{y} + 3\cdot(\frac{y-x}{y})^2 + 4\cdot(\frac{y-x}{y})^3 + \cdots] \\ &= \frac{x}{y}[1 + \frac{(1-\frac{x}{y})(1+\frac{x}{y})}{(\frac{x}{y})^2}] \\ &= \frac{x}{y} + \frac{y}{x}[1-(\frac{x}{y})^2] \\ &= \frac{x}{y} + \frac{y}{x} - \frac{x}{y} \\ &= \frac{y}{x} \end{aligned}$

到这里我们证得，通过一关的时间期望为 $\frac{\sum_{j=l_i}^i a_j}{a_i}$。

开个前缀和 $s$，通过一关的期望为 $\frac{s_i-s_{l_i}}{a_i}$。通过一段（左闭右开）关时间期望为：

$\begin{aligned} \sum_{j=l_i}^{r_i} \frac{s_j-s_{l_i}}{a_j} &= \sum_{j=l_i}^{r_i} (\frac{s_j}{a_j}-s_{l_i}\cdot\frac{1}{a_j}) \\ &= \sum_{j=l_i}^{r_i} \frac{s_j}{a_j} - s_{l_i}\sum_{j=l_i}^{r_i} \frac{1}{a_j} \end{aligned}$

显然两个都可以前缀和，记 $sa_i=\sum_{j=1}^i \frac{s_j}{a_j}$，$sb_i=\sum_{j=1}^i \frac{1}{a_j}$。

若确定了一个段，整段的期望时间可以 $\mathcal{O}(1)$ 求出。设 $f_{i,j}$ 表示考虑前 $i$ 关，已经分出了 $j$ 段的最优时间。转移方程为：

$f_{i,j}=\min_{k=1}^{i-1} ( f_{k,j-1}+ sa_i - sa_k + sb_k\cdot s_k - sb_i\cdot s_k )$

把只和 $i$ 有关的提出来，为：

$f_{i,j}=sa_i+\min_{k=1}^{i-1} ( f_{k,j-1} - sa_k + sb_k\cdot s_k - sb_i\cdot s_k )$

这东西显然是斜率优化。虽然被线性做法吊打但我还是要写李超。考虑李超树优化。把 $-s_k$ 当作斜率，$f_{k,j-1} - sa_k + sb_k\cdot s_k$ 当作截距。查询这个东西的最小值就是查询 $x=sb_i$ 和这些直线交点的最小值。

注意精度，动态开点的李超线段树存在较大的精度误差。考虑不动态开点，DP 转移中，$f_{i,j}$ 只由 $f_{k,j-1}$ 的转移过来。把李超树滚动一下就能过空间限制了。

代码

#include<cstdio>
#include<algorithm>
#define int long long // 要开 long long！
using namespace std;
const int max_n=1000005,inf=1000000000000000LL;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline int min(int a,int b){return a<b?a:b;}

int n,m,a[max_n],s[max_n];

double s1[max_n],s2[max_n];

struct LiChao{ // 不动态开点李超
	int p[max_n*4];
	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)

	double b[max_n],k[max_n];

	inline double slp(int j,int i){return b[i]+s2[j]*k[i];}
    // 计算 x=s2[j] 时直线的 y 值。不是算斜率

	inline void add(int x,int l,int r,int t){
		if(l==r){
			if(slp(l,t)<slp(l,p[x]))
				p[x]=t;
			return;
		}
		int mid=(l+r)>>1;
		if(slp(mid,t)<slp(mid,p[x]))
			t^=p[x]^=t^=p[x];
	
		if(slp(l,t)<slp(l,p[x])) add(ls(x),l,mid,t);
		else if(slp(r,t)<slp(r,p[x])) add(rs(x),mid+1,r,t);
	}
	inline double ask(int x,int l,int r,int t){
		if(!x) return 0;
		double res=slp(t,p[x]);
		if(l==r) return res;
		int mid=(l+r)>>1;
		if(t<=mid) return min(res,ask(ls(x),l,mid,t));
		return min(res,ask(rs(x),mid+1,r,t));
	}
	inline void clear(){ // 清空线段树，状压用
		for(register int i=0;i<=n;++i)
			k[i]=b[i]=p[i]=0;
	}
	#undef ls
	#undef rs
}seg[2]; // 滚动数组压在李超上

double f[max_n][2]; // 滚动 j 
double c[max_n];
int pos[max_n];

signed main(){
	n=read(),m=read();
	for(register int i=1;i<=n;++i){
		a[i]=read();
		s[i]=s[i-1]+a[i]; // s 即题解的 s
		s1[i]=1.0*s[i]/a[i], // s1 即题解的 sa
		s2[i]=1.0/a[i]; // s2 即题解的 sb
	}
	for(register int i=1;i<=n;++i){
		s1[i]+=s1[i-1],
		s2[i]+=s2[i-1];
		c[i]=s2[i]; // c 数组用于离散化
	}
	sort(s2+1,s2+1+n);
	for(register int i=1;i<=n;++i)
		f[i][0]=inf; // 初始化，分成 0 段是不合法的
	for(register int i=1;i<=n;++i)
		pos[i]=lower_bound(s2+1,s2+1+n,c[i])-s2;
	for(register int j=1,now=1;j<=m;++j,now^=1){
		seg[now].clear(); // 滚动掉过去的状态
		for(register int i=1;i<=n;++i){
			f[i][now]=s1[i]+seg[now].ask(1,1,n,pos[i]);

			seg[now].k[i]=-1.0*s[i];
			seg[now].b[i]=s2[i]*s[i]-s1[i]+f[i][now^1];
			seg[now].add(1,1,n,i);
		}
	}
	printf("%.10lf",f[n][m&1]);
	return 0;
}