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}$ 日元（日本货币）。赢零场的人不获得任何报酬。若可以任意操纵所有比赛的结果，求 $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}$

输出格式

输出答案。

2
2 5
6 5
2 1
7 9

15

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

4

提示

$1 \leq N \leq 16$ $1 \leq C_{i,j} \leq 10^9$ 输入中的所有数值均为整数。初始的人员排列为 $(1,2,3,4)$。 若人 $2$ 在与人 $1$ 的比赛中获胜，且人 $4$ 在与人 $3$ 的比赛中获胜，则队列变为 $(2,4)$。 之后，若人 $4$ 在与人 $2$ 的比赛中获胜，则队列变为 $(4)$，比赛结束。 此时，人 $2$ 恰好赢了 $1$ 场比赛，人 $4$ 恰好赢了 $2$ 场比赛，因此他们总共获得 $0+6+0+9=15$ 日元，这就是可能的最大总和。

标签: AtCoder|abc263F

来源

AtCoder|abc263F