做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 1429. -- 三取方格数

1429: 三取方格数

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 10
[上一题][提交][讨论版][状态][下一题]

题目描述

设有N*N的方格图,我们将其中的某些方格填入正整数, 而其他的方格中放入0。

某人从图的左上角出发,可以向下走,也可以向右走,直到到达右下角。

在走过的路上,他取走了方格中的数。(取走后方格中数字变为0)

此人从左上角到右下角共走3次,试找出3条路径,使得取得的数总和最大。

输入

第一行:N (4< =N< =20)

接下来一个N*N的矩阵,矩阵中每个元素不超过80,不小于0

输出

一行,表示最大的总和。

样例输入

4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4

样例输出

39

标签

[上一题][提交][讨论版][状态][下一题]