SP15576 STC09 - Aesthetic Text
题目描述
有一个由 $N$ 个单词组成的文本，这些单词按照顺序编号为 1 到 $N$。我们可以将这个文本分解成 $K$ 行，用一个数列 $(a_1, a_2, \ldots, a_{K-1})$ 来表示：从第 1 个单词到第 $a_1$ 个单词构成第一行，从第 $a_1+1$ 到第 $a_2$ 个单词构成第二行，依此类推，直到第 $K$ 行的最后单词。
每个单词有一个长度（字符数），用 $\text{length}(x)$ 表示第 $x$ 个单词的长度。同一行中，相邻的单词之间有一个长度为一个字符的空格。我们定义某一行的长度为该行所有单词长度的总和，再加上单词间空格的数量。用 $\text{line}(w)$ 表示第 $w$ 行的长度，如果第 $w$ 行从第 $i$ 个单词到第 $j$ 个单词，就有：
\[
\text{line}(w) = \text{length}(i) + \text{length}(i+1) + \cdots + \text{length}(j) + (j - i)
\]
举个例子，假设文本由 4 个单词组成，长度分别为 4、3、2 和 5，并且分解成 3 行，分解方式是 $(1, 3)$。那么这些行的长度分别是：第一行 4、第二行 6、第三行 5：
```
XXXX (第 1 行)
XXX XX (第 2 行)
XXXXX (第 3 行)
```
我们定义美学系数为各行长度差绝对值之和，即：
\[
|\text{line}(1) - \text{line}(2)| + |\text{line}(2) - \text{line}(3)| + \cdots + |\text{line}(K-1) - \text{line}(K)|
\]
如果分解只有一行，美学系数为 0。显然，美学系数越小，分解就越美观。
我们只考虑所有行的长度均不超过某一常数 $M$ 的分解，并在这些分解中找到美学系数最小的方案。对于示例中的分解，美学系数是 3，而在 $M = 6$ 和 $M = 7$ 时，这就是最小的美学系数。
### 你的任务：
编写一个程序：
- 从标准输入读取整数 $N$ 和 $M$，以及每个单词的长度，
- 计算每一行长度不超过 $M$ 的所有分解中美学系数的最小值，
- 将结果输出到标准输出。
### 输入格式：
第一行含有两个整数 $N$ 和 $M$，表示单词个数和行长度上限。第二行包含 $N$ 个整数，表示各个单词的长度。
### 输出格式：
输出一个整数，表示符合条件的分解中最小的美学系数。
### 数据范围与提示：
- $1 \le N \le 2000$
- $1 \le M \le 1000000$
- 每个单词的长度满足 $1 \le \text{length}(i) \le M$
### 示例：
对于输入：
```
6 4
4 3 2 5
```
输出应为：
```
3
```
对于另一个输入：
```
4 2
1 2
```
输出应为：
```
0
```
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无