內容
花花在方方城擁有多間房屋出租給上班族，今天又是每月的收租日，花花利用大好的天氣外出收租了。
花花的出租房屋分佈如下圖所示呈 N*N 的方陣形式(共有 N*N 間，橫軸、縱軸編號皆為 1~N)，花花從第(1,1)間開始收租，右下角為第(N,N)間。每間房屋的租金(M)並不相同(如果有需要設備維修，則租金扣掉維修費之後總數可能為負)。
花花本身又有一個習慣，一次出門收租只走一個來回，也就是從(1,1)走到(N,N)，再從(N,N)回到(1,1)就結束了，而去程途中花花只選擇向右、向下來走，回程途中花花只選擇向左、向上來走，請問花花此次出門最多可收取到多少的金額？ (注意同一間房屋租金只收取一次)
輸入說明
多筆測資(<=5筆)，每筆測資第一行一個整數N，代表有 N*N 間房; 接下來有N行，每行 N 個整數以一個空白間隔，代表每一間房可以收到的租金 M (已扣除維修費) 。 (2<=N<=50， -100000<=M<=100000)
輸出說明
每筆測資一行輸出，代表花花一趟來回可以收到的最大現金數。
範例輸入
#1
3 2 -3 9 -2 8 5 15 -3 10 2 -3 1 2 7 3 0 3 9 2 8 5 5 7 0
範例輸出
#1
35 7 34
測資資訊：
記憶體限制：
512
MB
提示 ：
DP
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||