考虑设 $f(i)$ 表示当机器人在 $i$ 时最优期望得分，那么对于 $i=1,n$ 有 $f(i)=a(i)$，否则有 $f(i)=\max(a_i,1/2(f(i-1)+f(i+1)))$，答案就是 $1/n\sum_{i=1}^nf(i)$。若把每个 $f(i)$ 当成未知数，那么这一组 $f(i)$ 就需要满足：

• $f(1)=a_1,f(n)=a_n$；
• $\forall 1＜i＜n$，$f(i)=1/2(f(i-1)+f(i+1))\ge a_i$ 或 $f(i)=a_i\ge1/2(f(i-1)+f(i+1))$。

考虑 $f(i)$ 一定满足 $f(i)\ge 1/2(f(i-1)+f(i+1))$，变形得到 $f(i)-f(i-1)\ge f(i+1)-f(i)$，也就是说 $f$ 是一个上凸壳，且凸壳的顶点一定是若干个 $(i,a_i)$。于是令 $P=\{(i,a_i)\}$，求出 $P$ 的上凸壳，最后对于 $f(i)$，若 $(i,a_i)$ 是凸壳顶点则 $f(i)=a_i$，否则设 $(i,a_i)$ 正上方直线为 $g(x)=kx+b$，那么 $f(i)=g(i)=ki+b$。