[COI 2023] Netrpeljivost

Luogu

IDLGP10755

Time1500ms

Memory512MB

Difficulty—

2023COI（克罗地亚）

午夜临近，是时候抓紧了。玛格丽塔成功地迎接了所有客人后，他们便在长桌旁安然落座。我们可以按照他们入座的顺序，将客人用从 1 到 $N$ 的数字进行标记。出于某种未知的原因，撒旦大舞会上的客人数量总是 2 的幂。然而，玛格丽塔现在遇到了一个难题，因为任意两位客人之间都存在一定程度的 **不和睦** (netrpeljivost)，我们可以用一个非负数来表示。客人 $i$ 和 $j$ 之间的不和睦程度我们记作 $netrp(i, j)$。并且总有 $netrp(i, j) = netrp(j, i)$ 以及 $netrp(i, i) = 0$。由于客人们已经（不怎么舒服地）坐定了，玛格丽塔不能大幅度地调整他们的顺序。客人们甚至不知道，他们自己其实身处一棵巨大的撒旦完全二叉树的叶子节点上，这棵树俗称 VSPBS，当 $N=4$ 时的情况如下图所示。 ![](https://cdn.luogu.com.cn/upload/image_hosting/xl062poz.png) (a) 图 1：初始的树结构，(b) 图 2：操作后的树结构玛格丽塔可以选择任意一个节点，并在一次操作中交换该节点的左、右孩子，从而改变对应叶子节点上客人的顺序。上图展示了当玛格丽塔对树的根节点进行一次操作后，树（以及餐桌）的状态。玛格丽塔可以对任意节点执行任意次操作。餐桌的总 **不和睦** 程度定义为所有相邻就坐的客人之间的不和睦程度之和。请帮助玛格丽塔计算出她能达成的餐桌总不和睦程度的最小值！ ## Input 第一行是一个正整数 $N$，表示客人的数量。在接下来的 $N$ 行中，第 $i$ 行（对于 $1 \le i \le N$）包含 $N$ 个整数，其中第 $j$ 个数代表 $netrp(i, j)$。这些值满足上文提到的性质。 ## Output 请输出题目所求的那个数值。 [samples] ## Background 题目来源：<https://hsin.hr/hio2023/>。 ## Note **【样例解释】** 在第二个例子中，一个可能的排列方式可以达到最小不耐受度的是 $2,1,4,3$。 **【数据范围】** 在所有子任务中，都满足 $1 \leq N \leq 2048$，且 $N$ 是 $2$ 的幂次，$0 \leq netrp(i,j) \leq 10^9$。 - 子任务 1（10 分）：$N\leq 16$； - 子任务 2（17 分）：$N\leq 128$； - 子任务 3（32 分）：$N\leq 512$； - 子任务 4（41 分）：无特殊限制；

Samples

Input #1

2
0 2
2 0

Output #1

Input #2

Output #2

Input #3

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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COI 2023] Netrpeljivost",
    "description": {
      "content": "午夜临近，是时候抓紧了。玛格丽塔成功地迎接了所有客人后，他们便在长桌旁安然落座。我们可以按照他们入座的顺序，将客人用从 1 到 $N$ 的数字进行标记。出于某种未知的原因，撒旦大舞会上的客人数量总是 2 的幂。 然而，玛格丽塔现在遇到了一个难题，因为任意两位客人之间都存在一定程度的 **不和睦** (netrpeljivost)，我们可以用一个非负数来表示。客人 $i$ 和 $j$ 之间的不和睦",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10755"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "午夜临近，是时候抓紧了。玛格丽塔成功地迎接了所有客人后，他们便在长桌旁安然落座。我们可以按照他们入座的顺序，将客人用从 1 到 $N$ 的数字进行标记。出于某种未知的原因，撒旦大舞会上的客人数量总是 2 的幂。\n\n然而，玛格丽塔现在遇到了一个难题，因为任意两位客人之间都存在一定程度的 **不和睦** (netrpeljivost)，我们可以用一个非负数来表示。客人 $i$ 和 $j$ 之间的不和睦...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments