b840: 104北二4.農作物採收問題
標籤 : 最大矩形和
通過比率 : 98% (56 人 / 57 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2016-06-20 12:04

內容

4.農作物採收問題 (104北二區 桃竹苗 )

問題描述

一個益智遊戲:有一塊面積為N×N的正方形(區分為N×N個單元)農地,玩家須在農地上找出最有效益的農作物採收區域,採收區域限制為連續區域(正方形或長方形),但不一定要從周圍開始採收,也可以通通不採收。但要注意{不是每一個單元的採收都有效益(加分)},採收到農作物尚未完全成熟的單元會造成虧損(扣分)!每個單元以一個整數來表示正或負的分數。正數代表有效益的採收單元及其得分,負數代表虧損的採收單元及其扣分。

範例一:以下左為一16單元的農地,以及其每一單元加、扣分: 而以下右為最有效益的採收區域:

0

-2

-8

1

 

 

 

 

 

 

 

 

11

2

-6

0

11

2

 

 

-1

-3

-9

12

-1

-3

 

 

1

9

0

-3

1

9

 

 

 

也就是說,最佳採收區域的得分為19分,出現在左下角的六個採收單元(11+2-1-3+1+9),其他的連續採收區域(正方形或長方形)的得分都比19小。 你的任務是:寫一程式計算出最佳採收區域的得分(最高得分)。

 

 

 

輸入說明

  輸入的第一列有一正整數 N(1<=N<=20),代表農地每一邊的長度。第二列開始有N×N個整數(值為-127~127、以空白鍵或換行鍵隔開),代表以列為主(row major)由左至右每個單元的分數。

 

輸出說明

最佳採收區域的得分(最高得分)

範例輸入
輸入範例一
4
0 -2 -8 1 11 2 -6 0 -1 -3 -9 12 1 9 0 -3
輸入範例二
2
0 -1 0 -3
範例輸出
輸出範例一
19
輸出範例二
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
提示 :
標籤:
最大矩形和
出處:
104北二區桃竹苗基資訊學科能力複賽 [編輯:
p3a_owhj (阿普二信)
]


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