P83212

蜂窝图问题

难度 5 级 初三 动态规划入门 线性
讨论 统计 2通过 5提交 40%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

如下图,是一个边长为 3 的蜂窝图,每个点有点权:

现在要从上面一行的某一点到最下面的一行某一点,每次只可以到达左下角的点和右下角的点,您最多可以交换选定的一行中的两个点的数值。

求通过交换,从上面一行的某一点到最下面的一行某一点的点权之和的最大值是多少。

输入

第一行一个整数 n 代表蜂窝图的边长。
接下来 2n-1 行每行若干个整数代表一个蜂窝图。

输出

一行一个整数代表答案。

样例

样例 1
输入
3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
输出
22

提示

样例说明

对于样例 1,交换第四行的 5 和 1,然后我们就可以得到一条点权之和最大的路径:

3 \to 2 \to 8 \to 5 \to 4

最大值为 22。

数据规模与约定

对于 100\% 的数据,1 \le n \le 99,0 \le 蜂窝图中的每个图 \le 99。

BalticOI 2000 Day1 A Honeycomb Problem。

来源

BalticOI

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交