← 返回题单

题单练习状态压缩DP

← 上一题下一题 →

A6197 | $Cube$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

你有一个边长为 $n$ 的三维立方体，里面有 $n^3$ 个整数。现在你的任务是从中挑选出 $n$ 个数，并且使得它们的总和最小。然而，选择的数不能位于同一个平面上。也就是说，在三维坐标系中，不能从相同的 $x$ 坐标、$y$ 坐标或 $z$ 坐标中选择两个数。

输入格式

输入首先是一个整数 $n$，表示立方体的大小。接下来是 $n^3$ 个整数，这些数按照 $n$ 个二维矩阵的形式给出，每个矩阵代表立方体的一层。具体来说，输入会有 $n^2$ 行，每行有 $n$ 个数。对于每个位置 $(x, y, z)$，其对应的数在第 $((x-1) \times n + y)$ 行的第 $z$ 列。 $2 \leq n \leq 12$ 立方体中的整数范围在 $0$ 到 $2 \times 10^7$ 之间。

输出格式

输出为一个整数，表示根据规则从立方体中选择的 $n$ 个数的最小和。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出