题解 CF643C 【Levels and Regions】

whiteqwq · 2020-09-07 23:41:02 · 题解

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]，它的期望为

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

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

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

然后开始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优，那么有：

然后拆括号，移项：

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

把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;
}