P3446 [POI 2006] EST-Aesthetic Text

让我们考虑一个由 $n$ 个单词组成的文本，这些单词从 1 到 $n$ 编号。我们用一个数列 $(a_1, a_2, \ldots, a_{k-1})$ 来表示将其分解为 $k$ 行的任意方式，使得编号从 1 到 $a_1$ 的单词在第一行，编号从 $a_1 + 1$ 到 $a_2$ 的单词在第二行，依此类推，最后编号从 $a_{k-1} + 1$ 到 $n$ 的单词在最后一行，即第 $k$ 行。 每个单词都有一定的长度（以字符数衡量）。令 $length(x)$ 表示第 $x$ 个单词的长度。此外，行中的每两个相邻单词之间用一个字符宽度的空格隔开。行的长度被定义为该行中单词长度的总和，加上它们之间的空格数。令 $line(w)$ 表示第 $w$ 行的长度。即，如果第 $w$ 行包含编号从 $i$ 到 $j$ 的单词（包括 $i$ 和 $j$），其长度为： ```cpp XXXX (第 1 行) XXX XX (第 2 行) XXXXX (第 3 行) ``` $$line(w) = length(i) + \ldots + length(j) + (j-i)$$ 例如，考虑一个由 4 个单词组成的文本，其长度分别为 4, 3, 2 和 5，以及将其分解为 3 行的方式 (1,3)。那么第一行的长度是 4，第二行是 6，第三行是 5： 我们称数值 $$|line(1) - line(2)| + \ldots + |line(k-1) - line(k)|$$ 为将给定文本分解为 $k$ 行的美学系数。特别地，如果分解只有一行，其美学系数为 0。 不言而喻，系数越小，分解越美观。我们只考虑那些没有行长度超过某个常数 $m$ 的分解。在所有这样的分解中，我们寻找最美观的，即美学系数最小的分解。上述示例分解的系数是 3，这正是 $m=6$ 和 $m=7$ 时美学系数的最小值。

标准输入的第一行包含两个数字 $m$ 和 $n$，$1 \le m \le 1\ 000\ 000$，$1 \le n \le 2\ 000$，以单个空格分隔。标准输入的第二行（也是最后一行）包含 $n$ 个整数，表示后续单词的长度，$1 \le length(i) \le m$ 对于 $i=1,2,\cdots,n$，以单个空格分隔。

标准输出的第一行且唯一一行应包含一个整数：对于那些每行长度不超过 $m$ 的分解，最小的美学系数。

题面翻译由 ChatGPT-4o 提供。