排版问题(Typesetting Problem)

题目描述

由于英文单词长短不一，对一篇文章进行排版的时候，要考虑均衡控制每行长度，达到整齐美观的效果。

给定一个整数 $N$，再给定 $N$ 个整数 $W_1,W_2,\dots,W_N$，表示有一篇文章，共有 $N$ 个单词，其中第 $i$ 个单词有 $W_i$ 个字母。

请为这篇文章的单词断行，整篇文章尽量美观，偏离度到达最小。

整篇文章的偏离度为每一行偏离度的和。单独一行的偏离度定义为 $(s-A)^2$，其中 $A$ 为一个给定的标准长度，$s$ 为这一行单词的字母数量之和。

输入格式

• 第一行：两个整数 $N$ 与 $A$；
• 第二行：$N$ 个整数 $W_1,W_2,\cdots,W_N$。

输出格式

• 单个整数：表示最小的排版偏离度。

样例输入 #1

10 20
8 9 4 5 7 3 4 9 9 3

样例输出 #1

3

样例说明 #1

| 8 9 4 | 5 7 3 4 | 9 9 3 |

每行之和分别为21、19、21，偏离度为 $1+1+1=3$。

样例输入 #2

7 10
3 5 1 3 4 6 4

样例输出 #2

8

数据范围

• $1\leq A\leq 100000$；
• $1\leq w_i\leq 100$；
• 对于 30% 的数据：$1\leq n\leq 25$；
• 对于 60% 的数据：$1\leq n\leq 5000$；
• 对于 100% 的数据：$1\leq n\leq 200000$。

知识点与难度

本题涉及的知识点从属于 GESP 8级（斜率优化动态规划），难度等级：⭐⭐⭐⭐。

测试点分布