思维好题-凸包-[USACO18DEC]Balance Beam-解题报告

· · 题解

首先计算：从i一直行动，到0或n停止，到n停止的概率？

f[0]=0,f[n+1]=1,f[i]=(f[i-1]+f[i+1])/2

解得f[i]=i/n

对于每个点，最优策略要么是直接跳下去，要么是疯狂玩，然后直到到达两边某个点，跳下去。把每个点画到坐标轴上，然后发现收益呈现一种线性关系（相似三角形），于是我们求出凸包，对每个点求贡献即可。

a,b$对位置$x$的贡献：$\frac{f(a)(b-x)+f(b)(x-a)}{b-a}

求凸包。

注意：下取整对加法没有分配律...

il void ins(const Node &v)
{
    while(tp>1&&cross(st[tp]-st[tp-1],v-st[tp-1])) --tp;
    st[++tp]=v;
}
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
#endif
    in(n);
    st[tp=1]=Node(0,0);
    for(ri i=1,t; i<=n; ++i)
    {
        in(t);
        ins(Node(i,t));
    }
    ins(Node(n+1,0));
    int p=1;
    const ull bas=100000;
    for(ri i=1; i<=n; ++i)
    {
        while(p<tp&&st[p+1].x<=i) ++p;
        if(st[p].x==i) printf("%llu\n",st[p].y*bas);
        else
        {
            ull a=st[p].x,b=st[p+1].x;
            ull ans=(st[p].y*bas*(b-i)+st[p+1].y*bas*(i-a))/(b-a);
            printf("%llu\n",ans);
        }
    }
    return 0;
}