[BZOJ5483][USACO18DEC]Balance Beam

传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=5483

Sol:

考虑一个长度为L的数轴

一个点向左走到0的概率是$frac{L-x}{L}$ 向右走到L的概率是$frac{x}{L}$

$ prove $:

设到一个点开始到L结束的概率是$ f_i $

$ f_i = f_{i-1} + f_{i+1} $ 可以发现是个等差数列的形式

求出$ f_i $ = $frac{L-x}{L}$ 

接下来我们就考虑 一个点上的答案是什么

显然的是，如果这个点继续走的期望比停下来的期望小，那么就直接结束

那么我们就可以从这个点想左和向右走，分别找到第一个继续走的期望比停下来的期望小的点

我们把这些点设成决策点

设一个点的左右决策点为$ A $ 和 $ B $

根据上面的引理得

$ E $=$ v_a*frac{b-i}{b-a} $ + $ v_b*frac{i-a}{b-a} $

然后就考虑怎么得到决策点

发现把$ (i, v_i ) $ 设成一个点

可以发现所有可能成为决策点的$(i, v_i )$形成了一个凸包

直接找出来然后转移就行了

#include <bits/stdc++.h>
using namespace std;
int Top;
const int Ned=1e5;
struct Vec{
    int x;long long y;
    Vec operator - (const Vec &A){Vec qwq;qwq.x=x-A.x;qwq.y=y-A.y;return qwq;}
    long long operator * (const Vec &A) {return (x*A.y-y*A.x);}
}P,Que[101000];
void Push(Vec Now){
    while (Top&&(Now-Que[Top])*(Que[Top]-Que[Top-1])<=0) --Top;
    Que[++Top]=Now;
}
int main(){
    int N;
    scanf("%d",&N);
    for (int i=1;i<=N;i++){
        Vec qwq;
        qwq.x=i;
        scanf("%lld",&qwq.y);
        qwq.y*=Ned;
        Push(qwq);
    }
    Vec qwqq;
    qwqq.x=N+1,qwqq.y=0;
    Push(qwqq);
    for (int i=1,j=0;i<=N;i++){
        while (j<Top&&Que[j].x<i) 
        ++j;
        if (Que[Top].x==i) printf("%lld
",Que[j].y);
        else printf("%lld
",((Que[j].x-i)*Que[j-1].y+(i-Que[j-1].x)*Que[j].y)/(Que[j].x-Que[j-1].x));
    }
    return 0;
}