题解 | #小苯的序列分割1.0#

题目链接

小苯的序列分割1.0

题目描述

给定一个长度为 $n$ 的序列 $a$ 和一个整数 $k$ 。需要将序列 $a$ 划分为恰好 $k$ 个非空的连续段。将每段的和组成一个新的序列 $b = \{b_1, b_2, \dots, b_k\}$ 。目标是最大化以下表达式的值：

$\sum_{i=1, i \text{ is odd}}^{k} b_i + \sum_{i=1, i \text{ is even}}^{k} b_i \times 2$

即新序列中奇数位置的段和贡献1倍，偶数位置的段和贡献2倍。

思路分析

这是一个典型的序列分割型动态规划问题。

1. 状态定义

我们定义 $dp[i][j]$ 为将原序列的前 $j$ 个元素（ $a_1 \dots a_j$ ）划分为 $i$ 段时，所能得到的最大目标值。

2. 状态转移

为了计算 $dp[i][j]$ ，我们需要考虑第 $i$ 段（也就是最后一段）是从哪里开始的。假设第 $i$ 段从索引 $p+1$ 开始，一直到 $j$ 结束。这意味着前 $p$ 个元素被划分成了 $i-1$ 段。

第 $i$ 段的和为 $\sum_{l=p+1}^{j} a_l$ 。为了快速计算，我们可以预处理一个前缀和数组 $S$ ，其中 $S[x] = \sum_{l=1}^{x} a_l$ 。那么该段的和就是 $S[j] - S[p]$ 。
第 $i$ 段的权重 $w_i$ 取决于 $i$ 的奇偶性：如果 $i$ 是奇数， $w_i = 1$ ；如果 $i$ 是偶数， $w_i = 2$ 。
因此， $dp[i][j]$ 可以从所有可能的 $dp[i-1][p]$ 转移而来，其中 $i-1 \le p < j$ 。

状态转移方程为： $dp[i][j] = \max_{i-1 \le p < j} \{ dp[i-1][p] + (S[j] - S[p]) \cdot w_i \}$

3. 复杂度与优化

直接实现上述转移方程，状态总数为 $O(k \cdot n)$ ，每次转移需要 $O(n)$ 的时间遍历 $p$ ，总复杂度为 $O(k \cdot n^2)$ ，会超时。

我们可以对转移方程进行变形： $dp[i][j] = \max_{i-1 \le p < j} \{ dp[i-1][p] - S[p] \cdot w_i \} + S[j] \cdot w_i$

对于固定的 $i$ 和 $j$ ， $S[j] \cdot w_i$ 是一个常数。我们需要最大化的是 $dp[i-1][p] - S[p] \cdot w_i$ 这一部分。

当我们按 $j$ 从小到大计算 $dp[i][j]$ 时， $p$ 的取值范围也在不断扩大。我们可以维护一个变量 $max\_prev\_term$ 来记录 $\max_{p} \{ dp[i-1][p] - S[p] \cdot w_i \}$ 的前缀最大值。

优化后的 $O(k \cdot n)$ 算法：

外层循环 $i$ 从 1 到 $k$ (段数)。
内层循环 $j$ 从 $i$ 到 $n$ (元素数)。
在计算 $dp[i]$ 这一“行”时，维护一个变量 $max\_prev\_term$ 。
- $max\_prev\_term = \max(max\_prev\_term, dp[i-1][j-1] - S[j-1] \cdot w_i)$
- $dp[i][j] = S[j] \cdot w_i + max\_prev\_term$

4. 空间优化

注意到 $dp[i]$ 的计算只依赖于 $dp[i-1]$ ，我们可以使用滚动数组，将空间复杂度从 $O(k \cdot n)$ 优化到 $O(n)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const long long INF = -1e18; // 使用一个足够小的数表示负无穷

void solve() {
    int n, k;
    cin >> n >> k;
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long val;
        cin >> val;
        s[i] = s[i - 1] + val;
    }

    vector<long long> dp(n + 1, INF);
    vector<long long> prev_dp(n + 1, INF);
    prev_dp[0] = 0; // 0个元素分成0段，和为0

    for (int i = 1; i <= k; ++i) {
        fill(dp.begin(), dp.end(), INF);
        long long w = (i % 2 != 0) ? 1 : 2;
        long long max_prev_term = INF;

        for (int j = i; j <= n; ++j) {
            // 更新 max_prev_term, p 的取值是 j-1
            max_prev_term = max(max_prev_term, prev_dp[j - 1] - s[j - 1] * w);
            if (max_prev_term > -1e17) { // 确保 max_prev_term 是有效的
                dp[j] = s[j] * w + max_prev_term;
            }
        }
        prev_dp = dp;
    }

    cout << dp[n] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    private static final long INF = -1_000_000_000_000_000_000L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[] s = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + sc.nextInt();
        }

        long[] prevDp = new long[n + 1];
        Arrays.fill(prevDp, INF);
        prevDp[0] = 0;

        long[] dp = new long[n + 1];

        for (int i = 1; i <= k; i++) {
            Arrays.fill(dp, INF);
            long w = (i % 2 != 0) ? 1 : 2;
            long maxPrevTerm = INF;

            for (int j = i; j <= n; j++) {
                // 更新 maxPrevTerm
                maxPrevTerm = Math.max(maxPrevTerm, prevDp[j - 1] - s[j - 1] * w);
                if (maxPrevTerm > -1e17) {
                    dp[j] = s[j] * w + maxPrevTerm;
                }
            }
            // 滚动数组
            System.arraycopy(dp, 0, prevDp, 0, n + 1);
        }

        System.out.println(prevDp[n]);
    }
}

import sys

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    s = [0] * (n + 1)
    for i in range(n):
        s[i+1] = s[i] + a[i]

    INF = float('-inf')
    
    prev_dp = [INF] * (n + 1)
    prev_dp[0] = 0
    
    for i in range(1, k + 1):
        dp = [INF] * (n + 1)
        w = 1 if i % 2 != 0 else 2
        max_prev_term = INF
        
        for j in range(i, n + 1):
            # p = j - 1
            max_prev_term = max(max_prev_term, prev_dp[j - 1] - s[j - 1] * w)
            if max_prev_term != INF:
                dp[j] = s[j] * w + max_prev_term
        
        prev_dp = dp

    print(prev_dp[n])

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：动态规划（带前缀和与状态转移优化）
时间复杂度： $O(k \cdot n)$ 。我们有两层主循环，分别遍历段数 $k$ 和元素数 $n$ 。
空间复杂度： $O(n)$ 。通过使用滚动数组，我们将DP表所需的空间从 $O(k \cdot n)$ 优化到了 $O(n)$ 。