题解

思路

对一个中间元素 $a_i$，合法拆分的两个数在 $s$ 的同一侧。为了使与相邻项相乘的代价最小，只需考虑合法范围的两个端点：

于是每个中间位置只有两种方向：$(x_i,y_i)=(u_i,v_i)$ 或 $(v_i,u_i)$。相邻项的贡献只依赖相邻两个位置各自的方向，可以使用两状态动态规划。

做法

处理第一个中间位置时，分别记录把 $u_2$ 或 $v_2$ 放在左侧的最小代价，其中包含 $a_1x_2$。

随后依次加入每个中间位置。对它的两种方向，枚举前一位置的两种方向，并加上 $y_{i-1}x_i$，取最小值。最后再分别加上 $y_{n-1}a_n$ 并取较小者。

端点拆分足够的原因是：固定相邻位置后，关于某个拆分变量的代价是线性的，在线性约束区间上的最小值必在端点取得。动态规划枚举了所有端点方向组合，因此得到全局最小值。

复杂度

每个位置只有两个状态和常数次转移。每个测试用例的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。