hrbust 1476 教主们毕业设计排版

题意

大四的教主们毕业了。
虽然是教主,但是毕业前都得拿出毕业设计才能得到学士学位,正式毕业。

毕业设计文档的排版有严格要求,排版上不能有一点错误,哪怕已经打印了,也要再修改文档重新打印,所以文档必须排版良好,整齐美观。

然后就有了如下求“整齐度”的简化的题目:
假设正文是$n$个长度分别为$L_1、L_2、……、L_n$(以字符个数度量,不计空白子字符)的单词构成的序列。我们希望将这个段落在一些行上整齐地打印出来,每行至多M个字符。“整齐度”的标准如下:如果某一行包含从i到j的单词$(i < j)$,且单词之间只留一个空格,则在行末多余的空格字符个数为$M - (j-i) - (L_i+ …… + L_j)$,它必须是非负值才能让该行容纳这些单词。我们希望所有行(除最后一行)的行末多余空格字符个数的立方和最小,这个立方和就是“整齐度”。

输入

有多组测试数据,每组测试数据有两行。
第一行为两个整数n, m,n(1<=n<=2000)表示单词个数, m(1<=m<=500)表示每行最多的字符数。
第二行为正文的n个单词的长度Li(1<=Li<=m),它们按在正文出出现的顺序给出。

输出

每组测试输出一行,包含一个整数,表示最优整齐度。

样例

input
5 5
4 1 1 3 3
5 6
1 3 3 2 3

output
17
1

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 2e4 + 10;
ll a[maxn], pre[maxn];
ll dp[maxn]; //dp[i]表示以i结尾的该行最后一个单词的最小整齐度
inline ll f(ll q)
{
return q * q * q;
}
int main()
{
int n, m;
while(cin >> n >> m)
{
memset(dp, 0, sizeof(dp));
memset(pre, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
{
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
//M为每行容纳的字符数
dp[0] = 0;
for(int i = 1; i <= n; i++)
{
dp[i] = dp[i - 1] + f(m - a[i]);
for(int j = i - 1; j >= 1; j--)
{
if(pre[i] - pre[j - 1] + i - j > m)
break;
dp[i] = min(dp[i], dp[j - 1] + f(m - pre[i] + pre[j - 1] - i + j));
}
}
// for(int i = 1; i <= n; i++)
// cout << dp[i] << endl;
ll ans = 1LL << 60;
for(int i = n; i >= 0; i--)//0表示一行就可以容纳所有单词
{
ans = min(ans, dp[i]);
if(pre[n] - pre[i - 1] + n - i > m)
break;
}
cout << ans << endl;
}

}