分数: 433 分
问题陈述
高桥负责展示 N 在艺术博物馆展览中连续绘画。
每幅画的编号为 1 to N和绘画 i 的色调值为 P_i。当画作排成一排时,相邻画作之间的色调值差异越大,给观看者带来的冲击力就越大。
展览空间有 N 位置从左到右排列,每个位置恰好放置一幅画。相邻位置之间有隔墙,总计 N - 1 隔墙。之间的隔墙 i从左边算起第一个位置和 (i + 1)从左边算起第一个位置有权重 W_i。观众更有可能在重量较大的墙壁前停下来,因此放置在此类墙壁附近的一对画作的影响力评价更高。
高桥使用所有 N 只绘制一次并将它们放置在 N 位置。让 Q_i 表示放置在 i从左边算起第一个位置。然后 (Q_1, Q_2, \ldots, Q_N) 是一个排列 (1, 2, \ldots, N)。展会综合评价得分计算公式为
\sum_{i=1}^{N-1} |P_{Q_i} - P_{Q_{i+1}}| \times W_i
其中 P_{Q_i} 代表绘画的色调值 Q_i 放置在 i从左边算起第一个位置。
高桥想要确定使评估分数最大化的绘画排列。给定音调值 P_1, P_2, \ldots, P_N 的 N 绘画和重量 W_1, W_2, \ldots, W_{N-1} 的 N - 1 隔墙,找出所有可能排列中的最大评价分数。
约束
- 2 \leq N \leq 16
- 1 \leq P_i \leq 10^7 (1 \leq i \leq N)
- 1 \leq W_i \leq 10^7 (1 \leq i \leq N-1)
- 所有输入值均为整数。
输入
N
P_1 P_2 \ldots P_N
W_1 W_2 \ldots W_{N-1}
- 第一行包含一个整数 N,绘画数量。
- 第二行包含 N 整数 P_1, P_2, \ldots, P_N 以空格分隔,代表画作的色调值。 P_i 是绘画的色调值 i.
- 第三行包含 N - 1 整数 W_1, W_2, \ldots, W_{N-1} 以空格分隔,代表隔墙的重量。 W_i 是之间的隔墙的重量 i从左边算起第一个位置和 (i + 1)从左边算起第一个位置。
输出
在单行上以整数形式输出最大评估分数。
示例输入 1
3 1 5 3 2 4
示例输出 1
20
示例输入 2
4 10 10 20 30 1 3 2
示例输出 2
110
示例输入 3
8 8 1 14 7 20 3 11 17 5 2 9 1 4 8 3
示例输出 3
422
示例输入 4
16 42 7 81 19 63 5 97 28 54 12 76 33 88 21 69 40 3 11 2 17 5 13 7 19 4 23 6 29 8 31 10
示例输出 4
11913
示例输入 5
2 1 10000000 10000000
示例输出 5
99999990000000