这是问题的简单版本。版本之间的差异在于,在这个版本中,对 $$$n$$$ 和测试用例数量的约束较小。只有解决了该问题的所有版本,您才能破解。
有 $$$n$$$ 个无限高度的连通器排列成一个圆圈。每个容器的底面积为 $$$1$$$ cm$$$^2$$$,并且在第 $$$i$$$ 个容器和第 $$$(i \bmod n) + 1$$$ 个容器之间,在高度 $$$h_i$$$ cm 处存在可忽略不计的体积连接。对于每个容器 $$$i$$$,求在第 $$$i$$$ 个容器保持空的情况下,可以放入这些容器中的最大总水体积(以 cm$$$^3$$$ 为单位)。
正式地,你会得到一个数组 $$$h_1, h_2, \ldots, h_n$$$。如果满足以下条件,则非负整数 $$$w_1, w_2, \ldots, w_n$$$ 的循环数组被称为良好:
- 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,如果 $$$\max(w_i, w_{i \bmod n + 1}) \gt h_i$$$,则 $$$w_i = w_{i \bmod n + 1}$$$。换句话说,如果数组$$$w$$$的两个相邻元素的最大值超过了数组$$$h$$$对应的元素,那么数组$$$w$$$的这两个相邻元素一定相等。
对于$$$1$$$到$$$n$$$中的每个$$$i$$$,在$$$w_i = 0$$$的条件下,输出所有好数组$$$w_1、w_2、\ldots、w_n$$$中可能的最大总和$$$w_1 + w_2 + \ldots + w_n$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 3000$$$) — 船只数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — 容器之间的分区的高度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个整数 - 第 $$$l$$$ 个整数表示在第 $$$l$$$ 个容器保持空的情况下,容器中的最大水总量(以 cm$$$^3$$$ 为单位)。
示例
输入复制
441 2 3 455 3 1 5 263 4 2 6 1 571 2 1 4 2 3 5
输出复制
6 6 7 917 16 14 14 1721 21 20 20 21 2117 17 17 17 21 21 22
注意
考虑第一个测试用例。
- 为了保持容器 $$$1$$$ 为空,一个好的数组是 $$$w = [0, 1, 2, 3]$$$,总共有 $$$6$$$ cm$$$^3$$$ 的水。
- 为了保持容器 $$$2$$$ 为空,一个好的数组是 $$$w = [1, 0, 2, 3]$$$,总共有 $$$6$$$ cm$$$^3$$$ 的水。
- 为了保持容器 $$$3$$$ 为空,一个好的数组是 $$$w = [2, 2, 0, 3]$$$,总共有 $$$7$$$ cm$$$^3$$$ 的水。
- 为了保持容器 $$$4$$$ 为空,一个好的数组是 $$$w = [3, 3, 3, 0]$$$,总共 $$$9$$$ cm$$$^3$$$ 水。
例如,数组 $$$w = [2, 2, 0, 4]$$$ 不好,因为 $$$\max(w_3, w_4) \gt h_3$$$,因此 $$$w_3 = w_4$$$ 必须成立。
可以证明,上面的每个数组在所有合适的选项中都具有最大可能的总和。