分数: 550 点
问题陈述
有一个圆形的蛋糕被切成了 N 按其半径进行相等的切片。
每件都标有一个整数 1 to N 按顺时针顺序,并且对于每个整数 i 与 1 \leq i \leq N,该作品 i 也称为片段 N + i.
最初,每件作品的颜色都是彩色 0.
您可以多次执行以下操作:
- 选择整数 a, b,和 c 这样 1 \leq a, b, c \leq N。对于每个整数 i 与 0 \leq i < b,改变棋子的颜色 a + i 着色 c。该操作的成本是 b + X_c.
你想要每件 i (对于 1 \leq i \leq N) 有颜色 C_i。找出实现这一目标所需的最低运营总成本。
约束
- 1 \leq N \leq 400
- 1 \leq C_i \leq N
- 1 \leq X_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
输出
打印答案。
示例输入 1
6 1 4 2 1 2 5 1 2 3 4 5 6
示例输出 1
20
让 A_i 表示棋子的颜色 i。最初, (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 0, 0, 0, 0).
执行操作 (a, b, c) = (2, 1, 4) 变化 (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 0, 0, 0, 0).
执行操作 (a, b, c) = (3, 3, 2) 变化 (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 2, 2, 2, 0).
执行操作 (a, b, c) = (1, 1, 1) 变化 (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 2, 2, 0).
执行操作 (a, b, c) = (4, 1, 1) 变化 (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 0).
执行操作 (a, b, c) = (6, 1, 5) 变化 (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 5).
在这种情况下,总成本是 5 + 5 + 2 + 2 + 6 = 20.
示例输入 2
5 1 2 3 4 5 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 2
5000000005
示例输入 3
8 2 3 3 1 2 1 3 1 3 4 1 2 5 3 1 2
示例输出 3
23