解题思路

给定一个固定的交替串 s=1010...（长度为 n），每次操作任选一个相邻位置 i，若 s[i] != s[i+1] 就能删除这两位并得到积分 a[i]。题目特别强调数组 a 在整个过程中不变，每次选择第 i 位都获得同一个 a[i]，可以重复选择同一个下标（只要当时还满足 i < len(s)）。

关键性质

1. 始终可选：交替串删除任意相邻一对后仍是交替串，因此每一步对所有 1..len(s)-1 的 i 都满足 s[i] != s[i+1]。
2. 步数固定：每次删去 2 个字符，直到长度 ≤ 1，因此操作次数固定为 m = ⌊n/2⌋。
3. 可选区间单调缩小：第 1 步可选下标为 1..(n-1)，第 2 步为 1..(n-3)，……，第 k 步为 1..(n-1-2(k-1))。注意数组 a 固定不变，且允许重复选同一下标。

于是问题变为：进行 m 次选择，第 k 次只能从前缀 1..r_k（r_k = n-1-2(k-1)）里取一个值 a[i]，并求所有步次得分之和的最大/最小值。

贪心 + 前缀极值

因为后续允许的集合始终是当前集合的子集（前缀长度减少 2），当前不取前缀最优只会让之后更难弥补。因此每一步的最优选择是：

• 最大值：在当下允许前缀里选前缀最大值；
• 最小值：在当下允许前缀里选前缀最小值。

令

• preMax[i] = max(a1..ai)
• preMin[i] = min(a1..ai)

则答案为

• Max = Σ preMax[r]，r 依次取 n-1, n-3, ..., (n%2==0 ? 1 : 2)
• Min = Σ preMin[r]，同样的 r 序列。

复杂度分析

• 预处理前缀最大/最小：O(n)
• 枚举需要的 m = ⌊n/2⌋ 个前缀点：O(m) 整体 O(n) 时间，O(n) 额外空间。对所有测试用例满足 ∑n ≤ 2×10^6 的限制。

代码实现

Python

import sys

def solve_case(n, a):
    # 计算前缀最大与前缀最小
    preMax = [0] * (n)
    preMin = [0] * (n)
    cur_max = -10**19
    cur_min = 10**19
    for i in range(1, n):  # i 对应前缀长度 i，使用 a[i-1]
        v = a[i - 1]
        if v > cur_max:
            cur_max = v
        if v < cur_min:
            cur_min = v
        preMax[i] = cur_max
        preMin[i] = cur_min

    # 累加 r = n-1, n-3, ...
    max_sum = 0
    min_sum = 0
    r = n - 1
    while r >= 1:
        max_sum += preMax[r]
        min_sum += preMin[r]
        r -= 2
    return max_sum, min_sum

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    T = next(it)
    out_lines = []
    for _ in range(T):
        n = next(it)
        a = [next(it) for _ in range(n - 1)]
        mx, mn = solve_case(n, a)
        out_lines.append(f"{mx} {mn}")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

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

/* ACM 风格：主函数处理输入输出，核心逻辑写成外部静态函数，类名 Main */
public class Main {

    // 计算一个用例的答案：返回 [maxSum, minSum]
    static long[] solveCase(int n, int[] a) {
        long[] preMax = new long[n];
        long[] preMin = new long[n];
        long curMax = Long.MIN_VALUE / 4;
        long curMin = Long.MAX_VALUE / 4;
        for (int i = 1; i <= n - 1; i++) {           // 前缀长度 i
            int v = a[i - 1];
            if (v > curMax) curMax = v;              // 维护前缀最大
            if (v < curMin) curMin = v;              // 维护前缀最小
            preMax[i] = curMax;
            preMin[i] = curMin;
        }
        long maxSum = 0, minSum = 0;
        for (int r = n - 1; r >= 1; r -= 2) {        // 依次取 n-1, n-3, ...
            maxSum += preMax[r];
            minSum += preMin[r];
        }
        return new long[]{maxSum, minSum};
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int T = Integer.parseInt(br.readLine().trim());
        for (int tc = 0; tc < T; tc++) {
            int n = Integer.parseInt(br.readLine().trim());
            int need = n - 1;
            int[] a = new int[need];
            int idx = 0;
            // 按空白分隔读取 n-1 个整数
            while (idx < need) {
                String line = br.readLine();
                if (line == null || line.isEmpty()) continue;
                String[] parts = line.trim().split("\\s+");
                for (String s : parts) {
                    if (s.isEmpty()) continue;
                    a[idx++] = Integer.parseInt(s);
                    if (idx == need) break;
                }
            }
            long[] ans = solveCase(n, a);
            out.append(ans[0]).append(' ').append(ans[1]).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

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

/* 计算一个用例的答案：返回 {maxSum, minSum} */
pair<long long, long long> solve_case(int n, const vector<int>& a) {
    vector<long long> preMax(n, LLONG_MIN / 4);
    vector<long long> preMin(n, LLONG_MAX / 4);

    long long curMax = LLONG_MIN / 4;
    long long curMin = LLONG_MAX / 4;
    // 前缀极值
    for (int i = 1; i <= n - 1; ++i) {
        int v = a[i - 1];
        if (v > curMax) curMax = v;   // 维护前缀最大
        if (v < curMin) curMin = v;   // 维护前缀最小
        preMax[i] = curMax;
        preMin[i] = curMin;
    }

    long long maxSum = 0, minSum = 0;
    // r 依次为 n-1, n-3, ...
    for (int r = n - 1; r >= 1; r -= 2) {
        maxSum += preMax[r];
        minSum += preMin[r];
    }
    return {maxSum, minSum};
}

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

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; 
        cin >> n;
        vector<int> a(n - 1);
        for (int i = 0; i < n - 1; ++i) cin >> a[i];

        auto ans = solve_case(n, a);
        cout << ans.first << ' ' << ans.second << "\n";
    }
    return 0;
}

题目内容

TK 得到了一个神奇的字符串 $s$ (下标从 $1$ 开始)，该字符串长度为 $n$，仅由 {$'0’,'1’$} 构成，并且对于任意的下标 $i$ ,若 $i$ $mod$ $2=1$ ，则 $s_i ='1’$，否则 $s_i='0’$ 。

此外，给定一个长度为 $n-1$ 的整数数组 {$a_1,a_2,…,a_{n-1}$}。你可以重复进行如下操作，直到无法继续；

• 选择一个下标 $i(1 ≦i< len(s))$，且满足 $s_i ≠ s_{i+1}$ ; 获得积分 $a_i$ ;删除 $s_i$ 与 $s_{i+1}$，其余字符按原顺序拼接成新串。

注意，数组 $a$ 在整个过程中不发生变化：每次选择的位置 $i$ 始终对应同一个 $a_i$ ; 数组的长度与元素值均保持不变。

请分别求出完成全部操作后，累计积分的最大值与最小值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦ T ≦ 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(2 ≦n ≦ 2 × 10^5)$ 表示字符串长度;

• 第二行输入 $n -1$ 个整数 $a_1,a_2,...,a_{n-1}(1 ≦ a_i≦ 10^9)$ 表示奖励积分数组。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出两个整数：

第一个整数表示累计积分的最大值，第二个整数表示累计积分的最小值。

样例1

输入

2
4
5 1 4
3
7 2

输出

10 6
7 2

说明

对于第一组测试数据原字符串 $1010$ 最小值操作方式：

• 选择 $s_2,s_3$ 得到 $1$ 积分，字符串变为 $10$

• 选择 $s_1,s_2$ 得到 $5$ 积分，字符串变为空无法操作结束。

总共获得 $6$ 积分，可以证明不存在比此积分更小的操作方式。