hrbust 1476 教主们毕业设计排版

发表于 | 分类于 |
字数统计: 677 | 阅读时长 ≈ 3

题意

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

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

然后就有了如下求“整齐度”的简化的题目：
假设正文是$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;
    }
    
}