← 返回题目列表

AtCoder · tkppc6_1_j

J. 两条路径

中文机器翻译题面 查看原题

配点 : 500 点

問題文

縦 N+1 方形,水平 N+1 我有一个正方形网格。左上角的正方形 (0,0) 、 (0,0) 下来 i 向右方格 j 前进 比方说 (i,j) 。

质量 那里放置了 (i,j)\ (0 \leq i,j \leq N) 有 A_{i,j} cookie。

执行以下操作。 执行 2 次。 选择通往

  • (0,0) 它们的编号最大为 (N,N) 的最短路线,并吃掉路线上方格上的所有饼干。 到

在这里, (0,0) 它们的编号最大为 (N,N) 的最短路径是 重复地从 (0,0) 垂直或水平移动到相邻的方块。 在到达 (N,N) 的路线中,它是经过最少方格的路线。

每次操作后,所选路线上方格内的cookie数量为 将会有 0 块。

找出最多可以吃多少块饼干。

制約

  • 1 \leq N \leq 200
  • 0 \leq A_{i,j} \leq 10^5\ (0 \leq i,j \leq N)
  • A_{0,0} = A_{N,N} = 0
  • 所有输入均为整数

入力

输入将以以下形式通过标准输入给出。

N
A_{0,0} A_{0,1} \cdots A_{0,N}
A_{1,0} A_{1,1} \cdots A_{1,N}
\vdots
A_{N,0} A_{N,1} \cdots A_{N,N}

出力

答案 对于 1 行输出。


入力例 1

2
0 1 1
1 2 1
1 1 0

出力例 1

7

通过以下操作, 你可以吃 7 饼干。


入力例 2

9
0 25273 26794 66830 40997 84165 45980 5843 80656 61575
87941 16379 8963 54856 64123 92048 30508 13499 63597 47707
23578 11427 93616 82855 28147 98207 67964 93434 32977 63765
51357 17333 43635 41603 984 97559 50230 50827 8012 67522
18345 2692 3452 69676 20584 88882 29554 11120 45476 1931
86655 70278 16349 93974 65638 22263 52541 55849 87916 18224
77866 70308 34053 17087 11677 84733 22083 66162 98308 2293
23288 68456 52353 44462 22185 20880 73802 87851 50133 56588
69248 59757 31414 72695 79497 30822 15037 76133 21699 45443
32105 6492 8375 65971 7857 72820 86156 24248 92835 0

出力例 2

2151343

原案 : 安道 作为