CF643C Levels and Regions解题报告

解题报告

---

CF643C Levels and Regions解题报告：

更好的阅读体验

题意

• 给定$n$个关卡$a_1\cdots a_n$，将这些关卡分成$m$段。
• 若第$i$段为$[l_i,r_i]$，那么对于$j\in[l_i,r_i]$，$1$小时通过$j$关卡的概率为$\frac{a_j}{\sum_{k=l_i}^j a_k}$。
• 求通过所有关卡的最少期望答案是多少个小时。
• 数据范围：$1\leqslant n\leqslant 200000,1\leqslant m\leqslant \min\{50,n\}$。

分析

比较好的dp题，把期望和斜率优化结合起来了。

首先，既然$1$小时通过$j$关卡的概率为$\frac{a_j}{\sum_{k=l_i}^j a_k}$，那么$j$关卡期望$\frac{\sum_{k=l_i}^j a_k}{a_j}$个小时通过，设$suma$为$a$的前缀和，那么$j$关卡期望$\frac{suma_j-suma_{l_i-1}}{a_j}$个小时通过。

然后，对于每一段$[l_i,r_i]$，它的期望为

$$\sum_{j=l_i}^{r_i}\frac{suma_j-suma_{l_i-1}}{a_j}$$

这里为了方便，我们把这一段改为$(k,r_i]$，即$k=l_i-1$。这样它的期望就是

$$\sum_{j=k+1}^{r_i}\frac{suma_j-suma_k}{a_j}=\sum_{j=k+1}^{r_i}(\frac{suma_j}{a_j}-\frac{suma_k}{a_j})=\sum_{j=k+1}^{r_i}\frac{suma_j}{a_j}-suma_k\sum_{j=k+1}^{r_i}\frac{1}{a_j}$$

我们设$b_i=\frac{1}{a_i}$，$sumb$为$b$的前缀和；$c_i=\frac{suma_i}{a_i}$，$sumc$为$c$的前缀和。

这一段的期望可以直接改为

$$sumc_{r_i}-sumc_k-suma_k\cdot(sumb_{r_i}-sumb_k)$$

然后开始dp，我们设$f_{i,j}$为从关卡$1$处理到关卡$j$，分$i$段的最小期望。

那么很显然有转移：$f_{i,j}=\min_{k=1}^{j-1}\{f_{i-1,k}+sumc_j-sumc_k-suma_k\cdot(sumb_j-sumb_k)\}$。

看到这个式子存在项$-suma_k\cdot sumb_j$，果断选择斜率优化。

设当时处理到$i$段，且存在两个$j$的决策点$x,y$满足$y<x<j$，且$x$比$y$优，那么有：

$$f_{i-1,x}+sumc_j-sumc_x-suma_x\cdot(sumb_j-sumb_x)\leqslant f_{i-1,y}+sumc_j-sumc_y-suma_y\cdot(sumb_j-sumb_y)$$

然后拆括号，移项：

$$(f_{i-1,x}-sumc_x+suma_x\cdot sumb_x)-(f_{i-1,y}-sumc_y+suma_y\cdot sumb_y)\leqslant suma_x\cdot sumb_j-suma_y\cdot sumb_j$$

因为$x>y$，所以$suma_x-suma_y>0$，所以可以两边同除$suma_x-suma_y$，不变号：

$$\frac{(f_{i-1,x}-sumc_x+suma_x\cdot sumb_x)-(f_{i-1,y}-sumc_y+suma_y\cdot sumb_y)}{suma_x-suma_y}\leqslant sumb_j$$

把$suma_k$看成$x$坐标，把$f_{i-1,k}-sumc_k+suma_k\cdot sumb_k$看成$y$坐标，这就是一个斜率的形式，直接上斜率优化板子就好了。

注意，因为这里是小于号，综合分析后应该取下凸壳。

时间复杂度：$O(nm)$，可以通过本题。

代码

#include<stdio.h>
#include<queue>
#define int long long
#define inf 10000000000000000
using namespace std;
const int maxn=200005,maxm=55;
int i,j,k,m,n,l,r;
int a[maxn],suma[maxn],q[maxn];
double b[maxn],c[maxn],sumb[maxn],sumc[maxn],f[maxm][maxn];
inline int x(int p){
    return suma[p];
}
inline double y(int p,int c){
    return f[c-1][p]+1.0*suma[p]*sumb[p]-sumc[p];
}
inline double slope(int a,int b,int c){
    if(x(a)==x(b))
        return y(a,c)>y(b,c)? inf:-inf;
    return 1.0*(y(a,c)-y(b,c))/(x(a)-x(b));
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        suma[i]=suma[i-1]+a[i];
        b[i]=1.0/a[i],sumb[i]=sumb[i-1]+b[i];
        c[i]=1.0*suma[i]/a[i],sumc[i]=sumc[i-1]+c[i];
    }
    for(i=1;i<=n;i++)
        f[0][i]=inf;
    for(i=1;i<=m;i++){
        l=1,r=0;
        q[++r]=0;
        for(j=1;j<=n;j++){
            while(l<r&&slope(q[l+1],q[l],i)<=sumb[j])
                l++;
            f[i][j]=f[i-1][q[l]]+sumc[j]-sumc[q[l]]-suma[q[l]]*(sumb[j]-sumb[q[l]]);
            while(l<r&&slope(j,q[r-1],i)<=slope(q[r],q[r-1],i))
                r--;
            q[++r]=j;
        }
    }
    printf("%.10lf\n",f[m][n]);
    return 0;
}