題意

給定一個(gè)數(shù)組，將數(shù)組劃分m組，要求每組的和的最大值最小

思路

算法1：dp

首先我們這樣考慮：我們要將前n個(gè)元素劃分成m段，即先找一個(gè)劃分點(diǎn)k，在[k + 1, n]不再劃分。然后將[1, k]劃分成m - 1段。那么就可以得到我們的狀態(tài)表示和轉(zhuǎn)移方程。

狀態(tài)表示：d[i,j]$d[i, j]$，前i個(gè)元素，劃分成j段的最大和。 轉(zhuǎn)移方程：d[i,j]=min{max0≤k<i{d[k,j?1]},∑p=k+1jap}$d[i, j] = min/{max_{0 /leq k <i}/{d[k, j - 1]/}, /sum/limits_{p=k+1}^{j}{a_p}/}$ 時(shí)間復(fù)雜度：O(n2m)$O(n^2m)$

算法2：二分

最大值最小問題一般采用二分答案的方法。

我們二分一下我們最后的答案，判斷答案是否合法即可。 判斷數(shù)x是否合法：統(tǒng)計(jì)一下將數(shù)組劃分為最大值≤x$/leq x$時(shí)能劃分多少組。如果組數(shù)cnt>x$cnt > x$，則說明我們答案應(yīng)該更大，否則，答案可以減小。

代碼