← 返回题目列表

Codeforces · 1499/C

C. 最小网格路径

中文机器翻译题面 查看原题

假设您站在 $$$XY$$$ 平面上的点 $$$(0, 0)$$$ 处,并且想要到达点 $$$(n, n)$$$。

您只能向两个方向移动:

- 向右,i。 e.水平方向和增加 $$$x$$$ 坐标的方向,
- 或向上,i。 e.垂直方向以及增加 $$$y$$$ 坐标的方向。

换句话说,您的路径将具有以下结构:

- 最初,你选择向右或向上;
- 然后你在所选方向上走了一些正整数距离(距离可以独立选择);
- 之后改变方向(从右到上,或从上到右)并重复该过程。

您不喜欢过多改变方向,因此方向更改不会超过 $$$n - 1$$$ 次。

因此,您的路径将是一条从 $$$(0, 0)$$$ 到 $$$(n, n)$$$ 的多边形链,最多由 $$$n$$$ 线段组成,其中每个线段的长度为正整数,并且垂直和水平线段交替。

并非所有路径都相同。您有 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$,其中 $$$c_i$$$ 是第 $$$i$$$ 段的成本。

使用这些成本,我们可以将路径的成本定义为该路径各段的长度之和乘以它们的成本,i。 e.如果路径由 $$$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$$$ 交替段组成。

示例

输入 #1

3
2
13 88
3
2 3 1
5
4 3 2 1 4

输出 #1

202
13
19

注意

在第一个测试用例中,要到达 $$$(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$$$。