e034: 收房租
標籤 :
通過比率 : 7人/8人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-01-27 07:15

內容

花花在方方城擁有多間房屋出租給上班族,今天又是每月的收租日,花花利用大好的天氣外出收租了。

花花的出租房屋分佈如下圖所示呈 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)

輸出說明

每筆測資一行輸出,代表花花一趟來回可以收到的最大現金數。

範例輸入
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
範例輸出
35
7
34
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1K
不公開 測資點#2 (70%): 1.0s , <1M
提示 :

DP

標籤:
出處:
林口高中校內選訓 [編輯:
hshua (hshua)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」