1794: 能量水晶(LNBS)(LongPeiyu)
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
现在有一个 N×N 的矩阵,在这个矩阵的每个格子都有若干能量水晶。现在,小明从这个矩阵的左边出发,目的地是这个矩阵的右边。当他走到一个格子时,他就能获得这个格子的能量水晶;
小明最开始会从左边的路边走到这个矩阵的第一列的任意一个格子里,当他处于这个矩阵的最后一列的时候,他必须往右走一步离开这个矩阵;
当他处于这个矩阵里时,每次只能从一个格子往右上方走一步或者往右下方走一步;
但是当他处于第一行时,就只能往右下方走;
同理,当他处于第N行时,就只能往右上方走。
现在要知道当他离开矩阵时获得的能量水晶最多能有多少。
输入
第一行为一个正整数 N;
接下来 N 行,每行 N个数,空格隔开,描述这个 N×N 的矩阵,每个数代表该格里面水晶的数目。
输出
一个数,表示小明离开矩阵时获得的能量水晶最多能有多少
样例输入 复制
3
1 2 3
3 2 1
2 3 1
样例输出 复制
7
提示
【样例1提示】
走路线2——2——3 或者 3——3——1
——————————————————————————————————————————————————————————————-
$20\%$的数据满足每个格子相等
$100\%$的数据满足$1\leqslant N \leqslant 1000$每个格子的数量均不超过$10$个
走路线2——2——3 或者 3——3——1
——————————————————————————————————————————————————————————————-
$20\%$的数据满足每个格子相等
$100\%$的数据满足$1\leqslant N \leqslant 1000$每个格子的数量均不超过$10$个