c409.
一、矩形選取(Rectangles)
Content
給你一個N×M的表格a，你必須從中選取非負整數個矩形，並且讓每次選擇矩形時，都滿足其嚴格在所有已選取矩形的右下角。
換言之，你不可以讓當前選取的矩形有任何的選取範圍X座標和Y座標小於或等於前面選取的任一個矩形範圍。
請寫一個程式計算你可以選取到的最大總和，即選取矩形裡所有數字的總和。
Input
每筆測試資料的首行會有兩個正整數N,M以空格隔開。
接下來有N行，每會有M個整數，第i行第j個數字代表aij。
Output
輸出一整數，代表你能圈選到的最大總和。
Sample Input
#1
5 4 5 3 -9 0 6 -1 7 11 -2 0 6 -10 -4 9 1 3 2 4 0 7
Sample Output
#1
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
不公開 測資點#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
Hint ：
本題共有三個子題，每一子題可有多筆測試資料：
第一子題的測試資料 N=1，M≤106，aij在int範圍內，全部解出可獲20分；
第二子題的測試資料 N,M≤3，aij在int範圍內，全部解出可獲20分；
第三子題的測試資料 N,M≤100，aij在int範圍內，全部解出可獲60分。
Tags:
出處:
板橋高中模擬賽
[管理者：
baluteshih
(波路特石)
]
| ID | User | Problem | Subject | Hit | Post Date |
|
沒有發現任何「解題報告」
|
|||||