START197B——Expected Cost 预期成本 · znzryb
## 思路讲解
精髓在于猜这个你随机跳到其他位置以后，再跳到终点N+1的期望成本，可以设这个东西位S，用这个S算出来的S，我们叫做g(S)。那么 $g(S)=S$ 那是必须的，但是我们猜的不等于怎么办呢？
于是我们就二分。
至于这个二分的收敛方向嘛，我试着推了一下，我的建议是都试试。guess嘛。
这个图把y=x画的太斜了，实际上在y=x的下面，$g(S)<S$，需要向左移动（也就是even<mid，r=mid）。
```cpp
// 从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代码
::: 源代码
```cpp
```
:::
## 心路历程（WA，TLE，MLE……）