← 返回题目列表

AtCoder · arc206_e

E. 矩形着色

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

分数: 800 点

问题陈述

有一个 N\times N 板,在哪里 N 至少 4。板子最外边缘不是角的单元格称为好单元格。更正式地说,其中 (i,j) 这样 1\leq i,j \leq N 和 i=1 or i=N or j=1 or j=N,排除的单元格 (1,1),(1,N),(N,1),(N,N) 被称为好细胞。在这里, (r,c) 指行中的单元格 r 和专栏 c.

所有好的单元格上都写有整数。该信息以四个长度的整数序列给出 N-2: U=(U_1,\ldots,U_{N-2}),D=(D_1,\ldots,D_{N-2}),L=(L_1,\ldots,L_{N-2}),R=(R_1,\ldots,R_{N-2}).

这些整数序列的每个元素对应于写在好单元上的整数,如下所示:

  • U_i: (1,i+1)
  • D_i: (N,i+1)
  • L_i: (i+1,1)
  • R_i: (i+1,N)

此外,板上的所有单元格最初都是白色的。您可以多次执行以下操作:

  • 选择两个在之前的操作中从未选择过的好单元格。设两个选出的好细胞为 (r_1,c_1) 和 (r_2,c_2)。对于所有人 (i,j) 满意 \min(r_1,r_2)\leq i \leq \max(r_1,r_2) 和 \min(c_1,c_2)\leq j \leq \max(c_1,c_2), 颜色 (i,j) 黑色。 操作的成本是写入两个选定的好单元格上的整数之和。

求将所有单元格涂成黑色所需的最小总成本。

回答 T 测试用例。

约束

  • 所有输入值均为整数。
  • 1 \leq T \leq 12500
  • 4 \leq N \leq 5\times 10^4
  • 0\leq U_i,D_i,L_i,R_i \leq 10^9
  • 总和 N 所有测试用例不超过 5\times 10^4.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
U_1 \ldots U_{N-2}
D_1 \ldots D_{N-2}
L_1 \ldots L_{N-2}
R_1 \ldots R_{N-2}

输出

输出 T 行。

对于 i第行,输出答案 i- 第一个测试用例。


示例输入 1

3
4
1 2
5 6
7 8
3 4
6
6 2 10 2
7 1 3 0
2 4 4 2
2 10 6 4
8
5 0 6 10 1 8
5 5 9 9 4 7
7 3 4 9 7 6
10 9 0 4 10 5

示例输出 1

36
15
21

在 1-st 测试用例,您可以将所有单元格涂成黑色,如下所示:

  • 执行选择操作 (1,2) 和 (3,4).
  • 执行选择操作 (2,4) 和 (4,2).
  • 执行选择操作 (4,3) 和 (2,1).
  • 执行选择操作 (3,1) 和 (1,3).

总成本为 (1+4)+(3+5)+(6+7)+(8+2)=36.

对于 2-nd 和 3-rd测试用例,输入板如下图所示: