1368. 三取方格数

时间限制 1000 ms   内存限制 128 MB

设有N*N的方格图,我们将其中的某些方格填入正整数, 而其他的方格中放入0。 某人从图得左上角出发,可以向下走,也可以向右走,直到到达右下角。 在走过的路上,他取走了方格中的数。(取走后方格中数字变为0) 此人从左上角到右下角共走3次,试找出3条路径,使得取得的数总和最大。

输入数据

第一行:N&nbsp &nbsp &nbsp (4< =N< =20)
接下来一个N*N的矩阵,矩阵中每个元素不超过80,不小于0

输出数据

一行,表示最大的总和。

样例输入

复制
4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4
 \n
 · · · \n
 · · · \n
 · · · \n
 · · · \n

样例输出

复制
39
  \n

样例说明

多进程DP

提交

请先 登录

© 2024 FAQs Contact About