c409: 一、矩形選取(Rectangles)
標籤 :
通過比率 : 83% (10 人 / 12 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2017-12-19 00:47

內容

  給你一個N×M的表格a,你必須從中選取非負整數個矩形,並且讓每次選擇矩形時,都滿足其嚴格在所有已選取矩形的右下角。
  換言之,你不可以讓當前選取的矩形有任何的選取範圍X座標和Y座標小於或等於前面選取的任一個矩形範圍。                                                          

  請寫一個程式計算你可以選取到的最大總和,即選取矩形裡所有數字的總和。

 

輸入說明

每筆測試資料的首行會有兩個正整數N,M以空格隔開。
接下來有N行,每會有M個整數,第i行第j個數字代表aij

輸出說明

輸出一整數,代表你能圈選到的最大總和。

範例輸入
5 4
5 3 -9 0
6 -1 7 11
-2 0 6 -10
-4 9 1 3
2 4 0 7
範例輸出
42
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (18%): 1.0s , <10M
不公開 測資點#1 (1%): 1.0s , <10M
不公開 測資點#2 (1%): 1.0s , <10M
不公開 測資點#3 (18%): 1.0s , <1K
不公開 測資點#4 (1%): 1.0s , <1K
不公開 測資點#5 (1%): 1.0s , <1K
不公開 測資點#6 (58%): 1.0s , <1M
不公開 測資點#7 (1%): 1.0s , <1M
不公開 測資點#8 (1%): 1.0s , <1M
提示 :

本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料 N=1,M≤106aij在int範圍內,全部解出可獲20分;
第二子題的測試資料 N,M≤3,aij在int範圍內,全部解出可獲20分;
第三子題的測試資料 N,M≤100,aij在int範圍內,全部解出可獲60分。

標籤:
出處:
板橋高中模擬賽 [編輯:
baluteshih (波路特石)
]


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