小苯的序列分割1.0

[牛客链接](https://www.nowcoder.com/practice/24c59dfa375e4d01b83689dd8f471b4b)

题意

给定长度为 $n$ 的序列 $a$ ，将其划分为恰好 $k$ 个非空的连续段，每段求和得到序列 $b$ 。最大化：

$ $\sum_{i=1}^{k} b[i] \cdot w_i$ $

其中奇数位置 $w_i = 1$ ，偶数位置 $w_i = 2$ 。

思路

把目标拆开看：

$ $\text{ans} = \sum_{\text{odd } i} b[i] + 2\sum_{\text{even } i} b[i] = \sum a[i] + \sum_{\text{even } i} b[i]$ $

因为所有 $b[i]$ 之和等于 $\sum a[i]$ （不管怎么分），所以第一项是定值。问题转化为最大化偶数位置段的总和 $S$ 。

把 $k$ 个段按奇偶交替排列：段 1（奇）、段 2（偶）、段 3（奇）……共 $m = \lfloor k/2 \rfloor$ 个偶数段。

用 DP 直接求解。定义 $dp[j]$ 为前 $i$ 个元素恰好分成 $j$ 段时，偶数段元素之和的最大值（ $i$ 是当前正在处理的元素）。

对于第 $i$ 个元素（从第 2 个开始遍历），它可以：

延续当前第 $j$ 段： $dp[j] \leftarrow dp[j]$ （+ $a[i]$ 若 $j$ 是偶数）
开启新的第 $j$ 段： $dp[j] \leftarrow dp[j-1]$ （+ $a[i]$ 若 $j$ 是偶数）

取两者较大值：

$ $dp[j] = \max(dp[j],\ dp[j-1]) + [j \text{ 为偶数}] \cdot a[i]$ $

初始化 $dp[1]=0$ （第一个元素在第 1 段，奇数段，贡献 0），其余为 $-\infty$ 。为避免覆盖， $j$ 从大到小更新。

最终答案为 $\sum a + dp[k]$ 。

以样例 1 验证： $a = [1,3,2,4,3]$ ， $k=4$ ， $m=2$ 。最优划分 $[1][3][2][4,3]$ 得 $b = \{1,3,2,7\}$ ， $S = 3 + 7 = 10$ ，答案 $= 13 + 10 = 23$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, k;
        scanf("%d%d", &n, &k);
        vector<long long> a(n);
        long long sumA = 0;
        for(int i = 0; i < n; i++){
            scanf("%lld", &a[i]);
            sumA += a[i];
        }
        int m = k / 2;
        if(m == 0){
            printf("%lld\n", sumA);
            continue;
        }
        const long long NEG_INF = -(long long)4e18;
        vector<long long> dp(k + 1, NEG_INF);
        dp[1] = 0;
        for(int i = 1; i < n; i++){
            for(int j = min(k, i + 1); j >= 1; j--){
                long long best = dp[j];
                if(j > 1 && dp[j-1] > NEG_INF)
                    best = max(best, dp[j-1]);
                if(j % 2 == 0)
                    dp[j] = (best > NEG_INF) ? best + a[i] : NEG_INF;
                else
                    dp[j] = best;
            }
        }
        printf("%lld\n", sumA + dp[k]);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            long[] a = new long[n];
            long sumA = 0;
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(st.nextToken());
                sumA += a[i];
            }
            int m = k / 2;
            if (m == 0) {
                sb.append(sumA).append('\n');
                continue;
            }
            final long NEG_INF = (long) -4e18;
            long[] dp = new long[k + 1];
            Arrays.fill(dp, NEG_INF);
            dp[1] = 0;
            for (int i = 1; i < n; i++) {
                for (int j = Math.min(k, i + 1); j >= 1; j--) {
                    long best = dp[j];
                    if (j > 1 && dp[j - 1] > NEG_INF)
                        best = Math.max(best, dp[j - 1]);
                    if (j % 2 == 0)
                        dp[j] = (best > NEG_INF) ? best + a[i] : NEG_INF;
                    else
                        dp[j] = best;
                }
            }
            sb.append(sumA + dp[k]).append('\n');
        }
        System.out.print(sb);
    }
}

复杂度分析

时间复杂度： $O(n \cdot k)$ 。每个元素遍历时更新 $k$ 个状态。
空间复杂度： $O(k)$ ，DP 数组。