CF1499C Minimum Grid Path

假设你站在 $XY$ 平面上的点 $(0, 0)$，你想要到达点 $(n, n)$。 你只能向两个方向移动： - 向右移动，即水平方向并且 $x$ 坐标增加； - 向上移动，即竖直方向并且 $y$ 坐标增加。 换句话说，你的路径将具有以下结构： - 最开始，你选择向右或向上； - 然后你在所选方向上前进一个正整数距离（每次距离可以独立选择）； - 之后你改变方向（从右变为上，或从上变为右），并重复上述过程。 你不喜欢频繁改变方向，因此你最多只会改变 $n-1$ 次方向。 因此，你的路径将是一条从 $(0, 0)$ 到 $(n, n)$ 的折线，由至多 $n$ 条线段组成，每条线段长度为正整数，且竖直和水平线段交替出现。 并不是所有路径都是等价的。你有 $n$ 个整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 表示第 $i$ 条线段的代价。 我们可以用这些代价定义路径的总代价：路径上每条线段的长度乘以其代价之和。即如果路径由 $k$ 条线段组成（$k \le n$），则总代价为 $\sum\limits_{i=1}^{k}{c_i \cdot length_i}$（线段按路径顺序编号 $1$ 到 $k$）。 请你找出总代价最小的路径，并输出其总代价。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$），表示每条线段的代价。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一行，表示从 $(0, 0)$ 到 $(n, n)$ 的总代价最小的路径的总代价，路径由至多 $n$ 条交替线段组成。

在第一个测试用例中，为了到达 $(2, 2)$，你至少需要转弯一次，因此路径恰好由 $2$ 条线段组成：一条长度为 $2$ 的水平线段和一条长度为 $2$ 的竖直线段。路径总代价为 $2 \cdot c_1 + 2 \cdot c_2 = 26 + 176 = 202$。 在第二个测试用例中，一条最优路径由 $3$ 条线段组成：第一段长度为 $1$，第二段长度为 $3$，第三段长度为 $2$。 总代价为 $1 \cdot 2 + 3 \cdot 3 + 2 \cdot 1 = 13$。 在第三个测试用例中，一条最优路径由 $4$ 条线段组成：第一段长度为 $1$，第二段长度为 $1$，第三段长度为 $4$，第四段长度为 $4$。总代价为 $1 \cdot 4 + 1 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 19$。 由 ChatGPT 4.1 翻译