AT_abc263_f [ABC263F] Tournament

题目描述

有 $2^N$ 个人，编号为 $1$ 到 $2^N$，进行一次“剪刀石头布”大赛。

比赛按照以下形式进行：

• 参赛者按照编号 $1, 2, \ldots, 2^N$ 的顺序横向排列成一列。
• 当前队列长度为 $2M$ 时，对于每个 $i\ (1\leq i \leq M)$，从左到右第 $2i-1$ 个人和第 $2i$ 个人进行比赛，输的 $M$ 个人被移出队列。如此重复 $N$ 次。

其中，第 $i$ 个人如果恰好赢了 $j$ 场比赛，则可以获得 $C_{i,j}$ 日元。如果一场都没赢，则得不到任何奖励。你可以自由决定所有比赛的胜负。请你求出编号为 $1,2,\ldots,2^N$ 的所有人最终能获得的奖金总和的最大值。

输入格式

输入通过标准输入给出，格式如下：

$N$
$C_{1,1}$ $C_{1,2}$ $\ldots$ $C_{1,N}$
$C_{2,1}$ $C_{2,2}$ $\ldots$ $C_{2,N}$
$\vdots$
$C_{2^N,1}$ $C_{2^N,2}$ $\ldots$ $C_{2^N,N}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
2 5
6 5
2 1
7 9

输出 #1

15

输入输出样例 #2

输入 #2

3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

输出 #2

4

说明/提示

限制条件

• $1 \leq N \leq 16$
• $1 \leq C_{i,j} \leq 10^9$
• 输入均为整数

样例解释 1

初始队列为 $(1,2,3,4)$。如果第 $1$ 个人和第 $2$ 个人比赛，第 $2$ 个人获胜，第 $3$ 个人和第 $4$ 个人比赛，第 $4$ 个人获胜，则队列变为 $(2,4)$。接着第 $2$ 个人和第 $4$ 个人比赛，第 $4$ 个人获胜，队列变为 $(4)$，比赛结束。此时，第 $2$ 个人恰好赢了 $1$ 场，第 $4$ 个人恰好赢了 $2$ 场，因此奖金总和为 $0+6+0+9=15$，这是可以获得的奖金总和的最大值。

由 ChatGPT 4.1 翻译