#PU864. USACO 2018 December Contest, Platinum — Problem 1. Balance Beam

    ID: 1264 传统题 文件IO:balance 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec18来源:usaco.orgscoring:equal_test_cases动态规划递推

USACO 2018 December Contest, Platinum — Problem 1. Balance Beam

USACO 2018 December Contest, Platinum — Problem 1. Balance Beam

题目描述

In order to save money for a new stall in her barn, Bessie the cow has started performing in the local circus, demonstrating her remarkable sense of balance as she carefully walks back and forth on an elevated balance beam! The amount of money Bessie earns in her performance is related to where she manages to ultimately jump off the beam.
The beam has positions labeled 0,1,…,N+10, 1, \ldots, N+1 from left to right.
If Bessie ever reaches 00 or N+1N+1 she falls off one of the ends of the beam and sadly gets no payment. If Bessie is at a given position kk, she can do either of the following:

  1. Flip a coin. If she sees tails, she goes to position k−1k-1, and if she sees heads, she goes to position k+1k + 1 (i.e. 12\frac{1}{2} probability of either occurrence).
  2. Jump off the beam and receive payment of f(k)f(k) (0≤f(k)≤109)(0 \leq f(k) \leq 10^9). Bessie realizes that she may not be able to guarantee any particular payment outcome, since her movement is governed by random coin flips. However, based on the location where she starts, she wants to determine what her expected payment will be if she makes an optimal sequence of decisions ("optimal" meaning that the decisions lead to the highest possible expected payment). For example, if her strategy earns her payment of 1010 with probability 1/21/2, 88 with probability 1/41/4, or 00 with probability 1/41/4, then her expected payment will be the weighted average 10(1/2)+8(1/4)+0(1/4)=710(1/2) + 8(1/4) + 0(1/4) = 7.

输入格式

The first line of input contains NN (2≤N≤1052 \leq N \leq 10^5). Each of the remaining NN lines contain f(1)…f(N)f(1) \ldots f(N).

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
1
3
150000
300000
Problem credits: Franklyn Wang and Spencer Compton