切換
舊版
前往
大廳
主題

ZeroJudge - d735: Minimum Sum 解題心得

Not In My Back Yard | 2019-10-13 17:42:04 | 巴幣 0 | 人氣 187

題目連結:


題目大意:
這題幾乎一樣,只差在這次是要求子區域總和最小之值為何。



範例輸入:
4
0  -2  -7   0  9  2  
-6   2  -4  
1  -4   1  -1  8   0  
-2 10 9 116 24 -121 30 14 2 119 122 28 -53 125 -71 87 -57 42 -111 125
-33 91 -121 30 -28 1 -16 97 -11 68 -24 103 -126 98 -61 33 48 109
-88 67 -72 77 -107 95 -78 23 -86 45 -4 28 -121 73 -57 20 -122 9
68 -97 79 -68 122 -42 88 -22 0 -116 55 -44 68 -109 43 -32 103 -54
122 -41 62 -114 113 -32 29 -22 99 -11 38 -60 88 -83 28 -83 122 -56
100 -86 63 -49 111 -77 91 -88 69 -110


範例輸出:
-17
-464


解題思維:
因為跟題目大意提及的那題只差在該題求最大,而本題求最小。

所以將本題中的陣列數字加上負號反轉後,再套用求最大子區域的方式做。最後將結果加上負號反轉回來就是所求。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

心彩
d206 我的 answer 初始為0 可以過 換到這題就不行了 (想說<0的情況不會發生 就完全不選就好了) 倒是發現考慮不周到的地方
2023-06-09 16:35:36
Not In My Back Yard
因為「最大連續子序列之和」有兩種類型,一種是可空(可以什麼數字都不選,所以 0 必定是答案的下界之一)、另一種就是不可空(因此下界被陣列中的數字所決定,而不一定是數字 0)。
2023-06-09 16:43:09
Not In My Back Yard
d206 那題在 UVa 原始題目其實有提到不可空(正確來說,它提到的是你至少要選 1 × 1 大小的子矩陣),不過搬移到 Zerojudge 上就失去這項資訊了。

我回去在我那篇心得文的題目大意補充一下好了。
2023-06-09 16:45:55
心彩
原來如此 d206跟UVA的測資 答案都是會>0 所以我才沒發現差異 今天是這題錯了 我才知道我寫錯了
2023-06-09 16:56:43

更多創作