[HNOI2008] 玩具装箱

题意

要把 n 件玩具按顺序分成若干连续段，每段放进一个容器。

若一段长度是 x，则费用是：

(x - L)^2

要求总费用最小。

思路

先看朴素 DP：

cpp

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#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 62);
const int MAXN = 5005;

int n;
long long L;
long long c[MAXN], sum[MAXN];
long long dp[MAXN];

long long X(int i) {
    return sum[i] + i;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据朴素 DP。
    // 枚举最后一个箱子从哪里开始。
    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        sum[i] = sum[i - 1] + c[i];
    }

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = INF;
        for (int j = 0; j < i; j++) {
            long long t = X(i) - X(j) - L - 1;
            dp[i] = min(dp[i], dp[j] + t * t);
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

设前缀和 sum[i] = C_1 + ... + C_i。

定义：

X(i) = sum[i] + i

如果最后一段是 j+1..i，那么这段容器长度减去 L 后，正好是：

X(i) - X(j) - L - 1

于是：

dp[i] = min(dp[j] + (X(i) - X(j) - L - 1)^2)

展开平方：

dp[i] = X(i)^2 + min(dp[j] + (X(j)+L+1)^2 - 2X(i)(X(j)+L+1))

这已经是标准斜率优化形式。

又因为 X(i) 单调递增，所以可以用单调队列维护候选决策点。

DP 转移方程

核心状态：

X(i)=sum[i]+i，dp[i] 为前 i 件最小费用

核心转移：

dp[i]=min(dp[j]+(X(i)-X(j)-L-1)^2)

答案收束：

dp[n]

代码

cpp

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

int n;
long long L;
long long c[MAXN], sum[MAXN];
long long dp[MAXN];
int q[MAXN];

long long X(int i) {
    return sum[i] + i;
}

long long S(int i) {
    return X(i) + L + 1;
}

long long Y(int i) {
    long long t = S(i);
    return dp[i] + t * t;
}

bool better_front(int a, int b, long long k) {
    return (__int128) (Y(b) - Y(a)) <= (__int128) k * (S(b) - S(a));
}

bool bad(int a, int b, int cidx) {
    return (__int128) (Y(b) - Y(a)) * (S(cidx) - S(b))
         >= (__int128) (Y(cidx) - Y(b)) * (S(b) - S(a));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        sum[i] = sum[i - 1] + c[i];
    }

    int head = 1, tail = 1;
    q[1] = 0;
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        long long k = 2LL * X(i);
        while (head < tail && better_front(q[head], q[head + 1], k)) {
            head++;
        }

        int j = q[head];
        long long t = X(i) - X(j) - L - 1;
        dp[i] = dp[j] + t * t;

        while (head < tail && bad(q[tail - 1], q[tail], i)) {
            tail--;
        }
        q[++tail] = i;
    }

    cout << dp[n] << '\n';
    return 0;
}

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

这题是非常典型的“分段平方代价 DP -> 展开平方 -> 斜率优化”。

记住 X(i) = sum[i] + i 这一步，后面的形式就会很自然。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。