分数: 500 点
问题陈述
有 N 孩子们从左到右站成一排。的活跃度 i左边第一个孩子是 A_i.
您可以按照您喜欢的任何顺序重新排列这些子项一次。
当一个孩子最初占据 x行中从左边算起的第一个位置移动到 y从左边数第 - 个位置,该孩子获得 A_x \times |x-y| 幸福点。
找出孩子们可以获得的最大总幸福分。
约束
- 2 \leq N \leq 2000
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 ... A_N
输出
打印孩子们可以获得的最大总幸福分。
示例输入 1
4 1 3 4 2
示例输出 1
20
如果我们移动 1-从左到右的第一个孩子 3- 从左边数第一个位置, 2- 第一个孩子 4- 第一个位置, 3-rd 孩子到 1-st 位置,以及 4第一个孩子 2-nd位置,孩子们赚到 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 幸福点数总计。
示例输入 2
6 5 5 6 1 1 1
示例输出 2
58
示例输入 3
6 8 6 9 1 2 1
示例输出 3
85