← 返回题目列表

Codeforces · 2041/C

C. 立方体

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

给你一个 $$$n\times n\times n$$$ 的大三维立方体,其中包含 $$$n^3$$$ 数字。您必须从这些数字中选择$$$n$$$,以使它们的总和尽可能小。但是,禁止选择位于同一平面上的两个数字。也就是说,如果我们通过三个笛卡尔坐标来确定立方体中的位置,那么如果 $$$x=x'$$$、$$$y=y'$$$ 或 $$$z=z'$$$,则禁止从位置 $$$(x,y,z)$$$ 和 $$$(x',y',z')$$$ 中选择两个数字。

输入

输入由数字 $$$n$$$ 和多维数据集中的 $$$n^3$$$ 数字组成。这些数字以 $$$n$$$ 二维矩阵表示,立方体的每一层都有一个。更准确地说,后面将有 $$$n^2$$$ 行,每行都有 $$$n$$$ 数字。对于每个 $$$x, y, z$$$ ($$$1\le x, y, z\le n$$$),位置 $$$(x, y, z)$$$ 处的数字被列为第 $$$((x-1)\times n+y)$$$ 行中的第 $$$z$$$ 个数字。

- $$$2 \leq n \leq 12$$$
- 立方体中的所有数字都是 $$$0$$$ 和 $$$2\times 10^7$$$ 之间的整数。

输出

输出由单个数字组成。它是根据上述规则从立方体中选择的 $$$n$$$ 个数字的最小和。

示例

输入 #1

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

输出 #1

5