杂题

题意

给定(n)，需要从(0)走到(n)，从(i)走到(i+1)成功的概率为(p_i)，如果不成功则返回(0)，不管成功与否均会花费一个单位的时间
幸运的是，可以放入(K)个读档器，若在(i)处失败了，只需要返回(jle i)的读档器(j)（(0)位置本身可以看做一个读档器）
问从(0)走到(n)的最小期望时间
本题的(p_i)给出的方法较为特殊，输入(F_0,F_1,cdots,F_{n})，(p_i=F_{i+1}/F_i)

(nle 10^5,Kle min(n,50),F_0ge F_1ge cdotsge F_{n})

做法

结论1：若(K=0)，则从(0)走到(n)的期望时间为(frac{sumlimits_{i=0}^{n-1}F_i}{F_n})

证明：
(ans=1+sumlimits_{i=0}^{n-2}(prodlimits_{j=0}^i p_j)+(1-prodlimits_{i=0}^{n-1}p_i)ans)

记(cost(l,r)=frac{sumlimits_{i=l}^{r-1}F_i}{F_r})
令(f(i,j))为放了(j)个读档器，其中第(j)个在位置(i)，从(0)走到(i)的最小期望时间

[f(i,j)=minlimits_{k}{f(k,j-1)+cost(k,i)} ]

结论2：对于任意(a<b<c<d)，有(cost(a,c)+cost(b,d)le cost(b,c)+cost(a,d))

于是可以通过分治解决，复杂度(O(Knlogn))