[USACO ?] Generic Cow Protests【来源请求】

题意

给出一个长度为 n 的序列，要把它完整划分成若干个连续组。

要求每一组的元素和都不小于 0，问最多能分成多少组。

思路

最直接的做法是暴力枚举所有切分方法。

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：暴力枚举最后一组的右端点，搜索所有合法分组方案。

const int MAXN = 35;
const int NEG_INF = -1000000000;

int n;
long long a[MAXN];
long long pre[MAXN];

// dfs(pos) 表示从第 pos 头牛开始分组，最多还能分出多少组。
int dfs(int pos) {
    if (pos > n) {
        return 0;
    }

    int best = NEG_INF;

    for (int r = pos; r <= n; r++) {
        long long seg_sum = pre[r] - pre[pos - 1];
        if (seg_sum >= 0) {
            int nxt = dfs(r + 1);
            if (nxt != NEG_INF) {
                best = max(best, 1 + nxt);
            }
        }
    }

    return best;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    int ans = dfs(1);
    if (ans == NEG_INF) {
        cout << "Impossible\n";
    } else {
        cout << ans << '\n';
    }
    return 0;
}

brute.cpp 的思路是：从当前位置开始，枚举当前组的右端点，只要这一段区间和非负，就递归处理后面的部分。

这个做法能帮助理解题意，但会反复搜索同一个前缀，效率太低。

更自然的想法是按前缀做 DP。

设：

dp[i] = 前 i 头牛最多能分成多少组

如果最后一组是区间 [j+1, i]，那么必须满足：

前 j 头牛已经能合法划分；
最后一组 [j+1, i] 的区间和非负。

于是就有转移：

dp[i] = max(dp[j] + 1)

其中 j < i，前 j 头牛本身已经可达，并且 sum(j+1..i) >= 0。

区间和可以用前缀和快速判断：

sum(j+1..i) = pre[i] - pre[j]

所以只要：

pre[i] - pre[j] >= 0

就说明 [j+1, i] 可以单独作为一组。

注意这里的前缀和含义必须统一：pre[i] 表示前 i 个数的总和，所以区间 [j+1,i] 的和是 pre[i] - pre[j]。但是只有 dp[j] 已经是合法状态时，才能用 dp[j] + 1 去更新 dp[i]，否则会把“不可能划分的前缀”也接到后面。

样例表

这张表展示样例里的关键状态：

`i`	前缀和 `pre[i]`	`dp[i]`	说明
0	`0`	`0`	空前缀
1	`2`	`1`	`[1,1]` 和为 `2`
2	`5`	`2`	`[1,1]`, `[2,2]`
3	`2`	`2`	最优是 `[1,2]`, `[3,3]` 不行；保留两组方案
4	`3`	`3`	可以分成 `[1,1]`, `[2,3]`, `[4,4]`

从表里可以看到，每次只要枚举最后一组从哪里开始，就能由更短前缀的答案转移过来。

如果整个序列根本不存在合法划分，应该输出 Impossible。

DP 公式

设前缀和为 $pre_i=\sum_{t=1}^i a_t$ ， $dp_i$ 表示前 $i$ 头牛最多能分成多少个合法组。初始化：

dp_0=0

若最后一组为 $(j+1..i)$ ，需要满足：

pre_i-pre_j\geqslant 0

于是转移为：

dp_i=\max_{0\leqslant j<i,\ dp_j\ 可达,\ pre_i-pre_j\geqslant 0}(dp_j+1)

最终答案为 $dp_n$ ；若不存在合法划分，则输出 Impossible。

公式解释：若最后一组是 j+1..i，它是否合法只由这段区间和决定。只要这段和非负，就可以在前 j 头牛的最优划分后再加一组，因此用 dp_j + 1 更新 dp_i。

代码

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

const int MAXN = 1005;
const int NEG_INF = -1000000000;

int n;
long long a[MAXN];
long long pre[MAXN];
int dp[MAXN];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    for (int i = 0; i <= n; i++) {
        dp[i] = NEG_INF;
    }
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // 前 j 头牛必须已经能合法划分，才可以接上最后一组。
            if (dp[j] == NEG_INF) {
                continue;
            }
            // 如果区间 [j+1, i] 的和非负，那么它可以作为最后一组。
            if (pre[i] - pre[j] >= 0) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    if (dp[n] == NEG_INF) {
        cout << "Impossible\n";
    } else {
        cout << dp[n] << '\n';
    }
    return 0;
}

复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

总结

这题的关键是把“整段划分”转成“最后一组放在哪里”的前缀 DP。

一旦前缀和能快速判断区间是否合法，转移就变得很直接。

一图流解析

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