划分型线性DP

划分型线性 DP

将序列划分为若干个非空连续段，求最优方案，是划分型线性 DP 的常见形式。

关键是枚举最后一段的起点：确定最后一段后，前面的部分仍是一个同类问题。

段数不限：通常用 $dp[i]$ 表示前 $i$ 个元素的最优答案。
段数固定：增加一维，用 $dp[i][j]$ 表示前 $i$ 个元素恰好分成 $j$ 段的最优答案。

下面两题都要求覆盖整个序列，每段非空，允许相邻。

例题一：奶牛分组

题目描述

$n$ 头奶牛按顺序排成一列，第 $i$ 头的理智度为 $a_i$ ，可能为负数。

将所有奶牛划分为若干个非空连续小组，每头奶牛恰好属于一组，要求每组理智度之和不小于 $0$ 。求最多能分成多少组，无解输出 Impossible。

输入：第一行一个整数 $n$ ，接下来 $n$ 行，每行一个整数 $a_i$ 。

输出：最多的组数，无解输出 Impossible。

范围： $1\le n\le1000$ ， $|a_i|\le10^5$ 。

一种最优划分为 [2]、[-1, 1]、[-2, 3]。

状态与转移

设 $dp[i]$ 表示前 $i$ 头奶牛全部分组时，最多可以分成多少组。

枚举最后一组为 $[j+1,i]$ 。用前缀和 $s$ 判断合法性：若 $s[i]-s[j]\ge0$ ，就可以在前 $j$ 头的合法方案后面增加一组。

$$dp[i]=\max_{\substack{0\le j<i\\s[i]-s[j]\ge0\\dp[j]\ne-1}}\bigl(dp[j]+1\bigr).$$

初始化 $dp[0]=0$ ，其余状态为 $-1$ ，表示不可达。最终看 $dp[n]$ ，为 $-1$ 时无解。

以样例为例，最后一组取 $[4,5]$ ，组内和为 $1$ ；前 $3$ 头最多分成 $2$ 组，因此得到 $dp[5]=dp[3]+1=3$ 。

必须检查前面的状态是否可达，不能只判断最后一组是否合法。

参考代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;
int n, dp[N];
long long a[N], s[N];

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

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

    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] != -1 && s[i] - s[j] >= 0) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

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

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

例题二：蜈蚣（异或和划分）

题目描述

给定长度为 $n$ 的序列 $a$ ，将整个序列划分为恰好 $m$ 个非空连续段。

每段的价值为段内所有数的按位异或和，求 $m$ 段价值之和的最大值。异或运算在 C++ 中用 ^ 表示。

输入：第一行两个整数 $n,m$ ，第二行 $n$ 个整数 $a_i$ 。

输出：恰好分成 $m$ 段时的最大价值。

范围： $1\le n\le1000$ ， $1\le m\le\min(n,100)$ ， $1\le a_i\le2^{30}-1$ 。保证最终答案不超过 $2^{30}-1$ 。

5 3
1 2 3 4 5

分为 [1, 2]、[3, 4]、[5]，价值之和为 $(1\oplus2)+(3\oplus4)+5=3+7+5=15$ 。

状态与转移

这次要求恰好分成 $m$ 段，需要记录已经划分的段数。

设 $dp[i][j]$ 表示前 $i$ 个数恰好划分成 $j$ 段的最大价值。

枚举最后一段为 $[k+1,i]$ ，前 $k$ 个数就必须恰好分成 $j-1$ 段。设前缀异或为 $s$ ，则最后一段的价值为 $s[i]\oplus s[k]$ ：

$$dp[i][j]=\max_{j-1\le k<i} \left(dp[k][j-1]+\bigl(s[i]\oplus s[k]\bigr)\right).$$

其中 $k\ge j-1$ ，保证前面有足够的元素组成 $j-1$ 个非空段；只从可达状态转移。

初始化 $dp[0][0]=0$ ，其余状态用 memset(dp, 0x80, sizeof(dp)) 设为很小的负数。由于合法价值非负，代码中可用 dp[k][j-1] < 0 判断不可达。最终答案为 $dp[n][m]$ 。

这里不能将所有状态初始化为 $0$ ，否则可能从“不足 $j-1$ 段”的状态转移，破坏“恰好”的限制。

参考代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005, M = 105;
int n, m, a[N], s[N];
long long dp[N][M];

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

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

    memset(dp, 0x80, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= min(i, m); ++j) {
            for (int k = j - 1; k < i; ++k) {
                if (dp[k][j - 1] < 0) continue;
                dp[i][j] = max(dp[i][j], dp[k][j - 1] + (s[i] ^ s[k]));
            }
        }
    }

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

时间复杂度 $O(mn^2)$ ，空间复杂度 $O(nm)$ 。

小拓展：选出的各段不能相邻

这个拓展改为选取若干个非空连续段，允许跳过元素，并要求两段之间至少空出一个元素。

设 $dp[i][j]$ 为前 $i$ 个元素中恰好选取 $j$ 段的最大价值。若最后一段为 $[l,i]$ ：

允许相邻时，从 $dp[l-1][j-1]$ 转移。
不允许相邻时，空出位置 $l-1$ ，改从 $dp[l-2][j-1]$ 转移，再加上最后一段的价值。

例如，最后一段选 $[5,7]$ ，就必须空出位置 $4$ ，前面的段只能在前 $3$ 个元素中选择。

由于可以不选位置 $i$ ，每个状态还要先继承 $dp[i-1][j]$ 。初始化所有 $dp[i][0]=0$ ，其余状态不可达； $l=1$ 时只能作为第一段，单独处理，避免访问负下标。