[HAOI2008] 木棍分割

题意

有 n 根木棍按顺序连在一起，允许最多切断 m 个连接处。

这样会把整列木棍分成若干段连续区间。

要求：

让所有区间中“总长度最大的一段”尽量小
输出这个最小值，以及达到这个最小值的方案数

方案数对 10007 取模。

思路

先看一个适合小数据验证的暴力：

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

const int MOD = 10007;

int n, m;
int a[25];
long long best_limit;
int ans;

void evaluate_mask(int mask) {
    int cut_cnt = 0;
    long long cur_sum = 0;
    long long max_seg = 0;

    for (int i = 1; i <= n; i++) {
        cur_sum += a[i];
        if (i == n || (mask & (1 << (i - 1)))) {
            max_seg = max(max_seg, cur_sum);
            cur_sum = 0;
            if (i != n) {
                cut_cnt++;
            }
        }
    }

    if (cut_cnt > m) {
        return;
    }
    if (max_seg < best_limit) {
        best_limit = max_seg;
        ans = 1;
    } else if (max_seg == best_limit) {
        ans++;
        if (ans >= MOD) {
            ans -= MOD;
        }
    }
}

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

    // brute.cpp：枚举所有切割方案，直接算每种方案的最大段长。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    best_limit = (1LL << 60);
    ans = 0;
    for (int mask = 0; mask < (1 << (n - 1)); mask++) {
        evaluate_mask(mask);
    }

    cout << best_limit << ' ' << ans << '\n';
    return 0;
}

暴力会枚举每个连接处切还是不切，直接算每种切法的最长段长度。

正解分成两步。

第一步先二分答案。

假设最长段长度上界是 lim，那么问题就变成：能不能把木棍分成至多 m+1 段，并且每段和都不超过 lim。

这个判定有单调性，所以可以二分。

判定时直接贪心从左到右尽量往当前段里塞木棍，算出最少需要多少段：

若最少段数 <= m+1，说明 lim 可行
否则不可行

这样就能得到最小可行上界。

第二步统计方案数。

固定最优上界 lim 后，设：

dp[s][i] 表示前 i 根木棍分成恰好 s 段，且每段和都不超过 lim 的方案数。

若最后一段是 (t+1..i)，只要它的区间和不超过 lim，就有：

dp[s][i] += dp[s-1][t]

对固定的 i 来说，满足条件的 t 会形成一个连续区间。

所以可以用双指针维护这个区间，再维护其中 dp[s-1][t] 的和，就把每个状态的转移降到 $O(1)$ 。

最后因为题目允许“最多切 m 刀”，也就是至多 m+1 段，所以把所有段数的 dp[s][n] 累加起来即可。

DP 转移方程

核心状态：

dp[s][i] 为前 i 根分 s 段的方案数

核心转移：

dp[s][i]+=sum dp[s-1][t] where sum(t+1,i)<=lim

答案收束：

sum_s dp[s][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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
const int MAXN = 50000 + 5;
const int MAXM = 1000 + 5;

int n, m;
int a[MAXN];
long long prefix_sum[MAXN];
int dp_prev[MAXN], dp_cur[MAXN];

bool check_limit(long long lim) {
    int seg_cnt = 1;
    long long cur_sum = 0;

    for (int i = 1; i <= n; i++) {
        if (a[i] > lim) {
            return false;
        }
        if (cur_sum + a[i] <= lim) {
            cur_sum += a[i];
        } else {
            seg_cnt++;
            cur_sum = a[i];
        }
    }
    return seg_cnt <= m + 1;
}

int count_ways(long long lim) {
    memset(dp_prev, 0, sizeof(int) * (n + 1));
    dp_prev[0] = 1;

    int ans = 0;
    for (int seg = 1; seg <= m + 1; seg++) {
        memset(dp_cur, 0, sizeof(int) * (n + 1));

        int left = 0;
        int window_sum = 0;
        for (int i = 1; i <= n; i++) {
            // 先把 t=i-1 加入窗口，表示最后一段只包含 a[i] 也是可能的。
            window_sum += dp_prev[i - 1];
            if (window_sum >= MOD) {
                window_sum -= MOD;
            }

            while (left < i && prefix_sum[i] - prefix_sum[left] > lim) {
                window_sum -= dp_prev[left];
                if (window_sum < 0) {
                    window_sum += MOD;
                }
                left++;
            }
            dp_cur[i] = window_sum;
        }

        ans += dp_cur[n];
        if (ans >= MOD) {
            ans -= MOD;
        }
        memcpy(dp_prev, dp_cur, sizeof(int) * (n + 1));
    }
    return ans;
}

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

    cin >> n >> m;
    long long left = 0, right = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        left = max(left, (long long)a[i]);
        right += a[i];
        prefix_sum[i] = prefix_sum[i - 1] + a[i];
    }

    while (left < right) {
        long long mid = (left + right) >> 1;
        if (check_limit(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    int ways = count_ways(left);
    cout << left << ' ' << ways << '\n';
    return 0;
}

复杂度

时间复杂度 $O(n \log(\sum L_i) + n \cdot m)$ ，空间复杂度 $O(n)$ 。

总结

这题最关键的是把“最优值”和“计数”拆开处理。

先二分最优上界，再在这个固定上界下做计数 DP，往往比试图一次把两个目标揉在一起更自然，也更容易写对。

一图流解析

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