START197B——Expected Cost 预期成本

思路讲解

精髓在于猜这个你随机跳到其他位置以后，再跳到终点N+1的期望成本，可以设这个东西位S，用这个S算出来的S，我们叫做g(S)。那么 $g(S)=S$ 那是必须的，但是我们猜的不等于怎么办呢？

于是我们就二分。

至于这个二分的收敛方向嘛，我试着推了一下，我的建议是都试试。guess嘛。

这个图把y=x画的太斜了，实际上在y=x的下面，$g(S)<S$，需要向左移动（也就是even<mid，r=mid）。

// 从x到N+1的最小期望成本
vdb dp(N+5);
DB l=0,r=accumulate(all(A),0ll)+accumulate(all(B),0ll);
FOR(_,1,100){
    DB mid=(l+r)/2;
    dp[N]=min((DB)A[N-1],mid+B[N-1]);
    ROF(i,N-1,1){
        dp[i]=min(dp[i+1]+A[i-1],mid+B[i-1]);
    }
    DB even=0;
    FOR(i,1,N){
        even+=dp[i];
    }
    // 包含位置 N+1 的 f=0（随机游走位置是包含N+1的）
    even/=(N+1);
    // 如果答案有问题，可以先换一下收敛方向
    // 我们要尽可能的减少这个even与这个mid之间的差
    if(even>mid){
        l=mid;
    }else{
        r=mid;
    }
}

AC代码

源代码

心路历程（WA，TLE，MLE……）