← 返回题目列表

AtCoder · awc0034_e

E. 展览布置

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

分数: 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