设前缀和 $S_i=\sum_{k=1}^i a_k$，把一段 $[j+1,i]$ 的代价改写为

$$\sqrt{\sum_{k=j+1}^i a_k-\tfrac12 a_i} =\sqrt{(S_i-\tfrac12 a_i)-S_j} =\sqrt{X_i-S_j}, \quad X_i:=S_i-\tfrac12 a_i. $$

于是

$$dp[i]=\min_{0\le j<i}\bigl(dp[j]+\sqrt{X_i-S_j}\bigr),\quad dp[0]=0. $$

由于 $a_i>0$，有

$$X_{i+1}-X_i=\tfrac12(a_{i+1}+a_i)>0,$$

因此查询点 $X_i$ 随 $i$ 严格递增。把每个候选 $j$ 看成函数

$$f_j(x)=dp[j]+\sqrt{x-S_j}\quad (x\ge S_j).$$

这些函数两两至多相交一次。

维护 lower envelope：按 $j$ 递增把 $f_j$ 依次加入，给每条新函数与当前尾部函数计算交点 $x^*$，把它当作新函数在下包络上的有效区间右端点。由于查询点 $X_i$ 单调递增，查询时只需从队尾弹出所有右端点 $\le X_i$ 的过期候选，当前队尾即为最优 $j$，从而得到 $dp[i]$。

设与尾部 $p$ 对比的新函数为 $q$，记

$$\Delta=dp[q]-dp[p],\qquad d=S_q-S_p>0.$$

则有三种情况：

• 若 $\Delta\le 0$，新函数 $q$ 在其定义域左端起就不劣，应弹出 $p$ 并继续与更旧者比；
• 若 $\Delta\ge\sqrt d$，两者无有效交点，$q$ 永不优，直接丢弃 $q$；
• 否则交点存在，其位置可由$$dp[p]+\sqrt{x-S_p}=dp[q]+\sqrt{x-S_q}$$ 化简得到$$x^*=S_p+\Bigl(\frac{\Delta+\frac d\Delta}{2}\Bigr)^2. $$若 $x^*$ 不大于当前尾部记录的右端点，则尾部无生存区间，需要继续弹出；否则把 $q$ 连同右端点 $x^*$ 入队。这样维护的分界点严格单调，因此每个候选最多入队出队一次，均摊查询 $O(1)$，总体 $O(n)$。