まず、少なくとも \(M\) 塊になるようにまとめるとありますが、かならずぴったり \(M\) 塊にまとめるとしてよいです。

さて数列 \(a\) のはじめの \(i\) 項を \(j\) 塊に分けるときのスコアを \(\mathtt { dp } [ i ] [ j ]\) とおきます。\(a\) の累積和を \(\tilde a _ i = \sum _ { j < i } a _ j\) で定めると、\(\mathtt { dp }\) は次のように計算できます。

\[ \mathtt { dp } [ i ] [ j ] = \min \left \lbrace \begin{array}c \min \left \lbrace \mathtt { dp } [ i - 1 ] [ k ] + \tilde a _ k - \tilde a _ j \middle \vert k < j , a _ k > a _ j \right \rbrace \\ \min \left \lbrace \mathtt { dp } [ i - 1 ] [ k ] - \tilde a _ k + \tilde a _ j \middle \vert k < j , a _ k < a _ j \right \rbrace \\ \end{array} \right \rbrace \]

これをそのまま計算すると遅いですが、\(\mathtt { dp } [ i ]\) を左から順に計算する過程で \(\mathtt { dp } [ i - 1 ] [ k ] \pm \tilde a _ k\) の値を \(\tilde a _ k\) をキーとしたセグツリーで管理しておくと、高速に求めることができます。