Cut the Sequence

題目link：http://poj.org/problem?id=3017

Part1：

首先拿到這道題，先得出普通的 dp。

設 f_i 表示将前 i 個數按最優方案分為幾個合法的區間的最大值之和。

那麼容易得出 dp 方程：

f_i = min{ f_j + Max(j + 1, i) } (0 ≤ j ≤ i - 1 && Sum(j + 1, i) ≤ m);

其中 Max(x, y) 表示 max{ a_i } (x ≤ i ≤ y)，Sum(x, y) 表示 Σ a_i (x ≤ i ≤ y)。

Part2：

這時容易發現這個題很難直接用單調隊列進行優化，那麼考慮通過決策單調性來考慮這個問題。

那麼就來考慮用哪個 j 來轉移最優。

但是顯然這個并不是太好考慮，那先來考慮用 j 來轉移比用 j - 1 來轉移更優的條件是什麼。

容易得出隻有兩種情況：

Sum(j, i) > m && Sum(j + 1, i) ≤ m；

f_j + Max(j + 1, i) < f_{j - 1} + Max(j, i)；

那麼滿足這兩種情況之一就變成了 j 是最優轉移的必要條件。

但是好像這個題不能像普通的單調隊列優化 dp 的題一樣來找到隊首這樣一個唯一的最優解，那麼現在隻能去考慮一下找到一些 j，使得最優的轉移包含在這些 j 裡面就行了（dp 雖然需要不漏，但是不需要不重）。

那麼現在就考慮如何去找到上面的兩種情況的 j 并依次進行轉移就行了。

Part2.1：

這裡第一種情況比較容易考慮。

容易得到對于每一個 i 來說，這樣的 j 隻可能會存在一個（因為它是一個分界點）。

然後就可以二分去找這樣的 j，具體實作可以使用 STL 中的 lower_bound 函數（找到第一個大于或等于 Sum(1, i) - m 的 Sum(1, j)，j 就是答案）。

Part2.2：

這裡可能會較為困難一些，那麼先看一看 f_j 和 f_{j - 1} 的關系。

它們的關系其實是 f_j ≥ f_{j - 1}，這裡給出證明：

考慮使用前 j 個數的最優分區間方案的分界點去分前 j 個數，這裡容易證明這樣是一個分前 j - 1 個數的合法的方案，但不一定是最優的方案，并且也容易證明這樣分的所有區間最大值之和是小于或等于前 j 個數的最優方案的所有區間最大值之和的（因為隻會有最後一個區間的數比前 j 個數的方案的最後一個區間的數少一個，但是最後一個區間的最大值不可能比前 j 個數的大）。是以既然如這般如此，僅僅是一個合法的方案就比前 j 個數的最優方案要好（或相等），那 f_j 一定大于或等于 f_{j - 1}，證畢。