Solution for Codeforces Problem 1373D - Maximum Sum on Even Positions

· · 题解

本文将同步到 Hexo 博客.

本题给定了一个数组 a_0, a_1, \cdots, a_{n - 1}, 求翻转一段连续区间之后, 下标为偶数的所有数之和最大.

可以转换一下思路: 选定一段区间之后, 那段区间内取的是下标为奇数的数之和而不是下标为偶数的数之和. 这样就可以用 DP 来解决.

需要注意的是, 如果区间的长度为奇数, 那么头与尾的数必须要舍弃一个.

举个例子 (以下红色标注的是计入最终答案的数, 框是选择的区间):

\color{red}a_0, \color{none}\boxed{\color{none}{a_1}, \color{red}a_2, \color{none}a_3, \color{red}a_4, \color{none}a_5}, \color{red}a_6, \color{none}a_7

这是错误的:

\color{red}a_0, \color{none}\boxed{\color{red}{a_1}, \color{none}a_2, \color{red}a_3, \color{none}a_4, \color{red}a_5}, \color{red}a_6, \color{none}a_7

正确:

这种取法相当于区间 [1, 4] 翻转

\color{red}a_0, \color{none}\boxed{\color{red}{a_1}, \color{none}a_2, \color{red}a_3, \color{none}a_4, \color{none}a_5}, \color{red}a_6, \color{none}a_7

这种取法相当于区间 [2, 5] 翻转

\color{red}a_0, \color{none}\boxed{\color{none}{a_1}, \color{none}a_2, \color{red}a_3, \color{none}a_4, \color{red}a_5}, \color{red}a_6, \color{none}a_7

还有一种避免像上面的错误情况出现, 那就是避免选奇数长度的区间, 但由于这样太麻烦, 所以可以分两种情况 DP: 一种是头取的情况, 另一种是尾取的情况. 具体见代码.

// 注意, 代码中的下标一律从 1 开始
// 所以奇偶性与题面中一律相反
// 下面注释中的 "下标" 一律指题面中的下标
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int cnt_test;
int n;
ll a[200001];
ll f[200001][4]; // DP
// 第二维:
// 0: 所选区间左侧的数 (下标为偶数)
// 1: 所选区间内的第一个数取, 最后一个数不取 (下标为奇数)
// 2: 所选区间内的第一个数不取, 最后一个数取 (下标为奇数)
// 3: 所选区间右侧的数 (下标为偶数)
ll ans;

template <typename T>
inline T read() {
    T x = 0;
    T multiplier = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            multiplier = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar();
    }
    return x * multiplier;
}

int main() {
    cnt_test = read<int>();
    while (cnt_test--) {
        n = read<int>();
        for (int i = 1; i <= n; i++) {
            a[i] = read<ll>();
            f[i][0] = f[i][1] = f[i][2] = f[i][3] = 0; // 初始化
        }
        for (int i = 1; i <= n; i++) {
            if (!(i & 1)) { // 当前下标为奇数
                f[i][1] = f[i - 1][0] + a[i];
                if (i == 2) {
                    f[i][2] = a[i];
                }
                if (i >= 4) {
                    f[i][2] = f[i - 3][0] + a[i];
                    f[i][1] = max(f[i][1], f[i - 2][1] + a[i]);
                    f[i][2] = max(f[i][2], f[i - 2][2] + a[i]);
                }
            } else { // 当前下标为偶数
                if (i == 1) { // 特判, 以防超界
                    f[i][0] = a[i];
                } else if (i >= 3) { // 直接转移
                    f[i][0] = f[i - 2][0] + a[i];
                }
                if (i >= 3) {
                    // 所选区间内的最后一个数取, 因此从上一个数转移
                    f[i][3] = f[i - 1][2] + a[i];
                }
                if (i >= 5) {
                    f[i][3] = max(
                        { f[i][3], f[i - 3][1] + a[i], f[i - 2][3] + a[i] });
                    // max 内的值分别表示:
                    // f[i][3] 原来的值
                    // 所选区间内最后一个数不取, 因此从当前位置之前的第三个数转移
                    // 直接从上一个下标为偶数的数转移
                }
            }
        }

        ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max({ ans, f[i][0], f[i][1], f[i][2], f[i][3] });
        }
        printf("%lld\n", ans);
    }
    return 0;
}