题解 P5155 【[USACO18DEC]Balance Beam】

分步证明，首先抛出结论：每个点的策略要么是不动，要么是随机移动直到左右两个点中的一个落下。

结论1：从点x开始在a和b之间移动在b落下的概率为 (x-a)/(b-a)

设概率为f[x]=k,则f[a]=0,f[b]=1。因为x有1/2几率往左走或往右走，所以
f[x]=(f[x-1]+f[x+1])/2
即f(x)满足等差数列的性质，则图像为由(a,0),(b,1)组成的直线，做两条垂线做相似三角形即可。从b到a反过来即可。

结论2：ans(x)=max(val[x],(val[a](b-x)/(b-a)+val[b](x-a)/(b-a))/2)

期望的基本概念，贡献*概率的平均数

结论3：若最优策略为使一个点在两个停止点之间移动则停止点的连线为一个凸包

若一个在凸包内的点为停止点，则在该停止点的期望计算为它本身的贡献值，但实际上若以原本就在它两侧的停止点计算贡献使贡献更高（凸包的定义）

结论4：最优策略就是在两个停止点之间移动

无论是什么策略，在本题中必然有停止下来的点，而且必然有两个以上。
若只有一个停止点，可实际上到达0或n+1时点必定会停下来，故至少有两个停止点
若有大于两个的停止点，则在到达一个停止点（非边界处）可以选择停或不停，若不停相当于这个点不是停止点，若停就相当于这个点就是停止点，无法再延伸。因为在本题中无论你何时到达x点，你的状态都是相同的，不存在根据不同的状态来选则的策略，故不存在大于两个的停止点（会不会有点绕）

#include<bits/stdc++.h>
using namespace std;
const long long K=100000;
inline long long read()
{
    long long num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
struct gzw
{
    long long x,y;    
}p,q[500009];
inline gzw operator -(gzw a,gzw b)
{
    return (gzw){a.x-b.x,a.y-b.y};    
}
inline long long operator *(gzw a,gzw b)
{
    return     a.x*b.y-a.y*b.x;
}
long long tail;
long long n;
void push(gzw x)
{
    while(tail&&(x-q[tail])*(q[tail]-q[tail-1])<=0) tail--;
    q[++tail]=x;
}
int main()
{
    n=read();
    for(long long i=1;i<=n;i++)
    {
        p.x=i;
        p.y=read()*K;
        push(p);    
    }
    push((gzw){n+1,0});
    for(long long i=1,j=0;i<=n;i++)
    {
        while(j<tail&&q[j].x<i) j++;
        if(q[j].x==i) printf("%lld\n",q[j].y);
        else printf("%lld\n",((q[j].x-i)*q[j-1].y+(i-q[j-1].x)*q[j].y)/(q[j].x-q[j-1].x));
    }
    return 0;
}