Linear Programming Formulation

Let (\cdot) denote the dot product, with (b,c,x,y) as row vectors. For matrix (A), vectors (u,v) satisfy (u \leq v) if (\forall i, u_i \leq v_i), and similar for (\geq).

The standard linear programming (LP) problem is:

[\max c \cdot x \quad \text{s.t.} \quad \begin{cases} Ax \leq b \ x \geq 0 \end{cases}]

Its dual is:

[\min b \cdot y \quad \text{s.t.} \quad \begin{cases} A^T y \geq c \ y \geq 0 \end{cases}]

Weak duality theorem: (\max c \cdot x \leq \min b \cdot y). This holds because for any feasible (x,y), we have (y^T A x \leq y^T b = b \cdot y) and (y^T A x = (A^T y)^T x \geq c^T x = c \cdot x).

Strong duality theorem: (\max c \cdot x = \min b \cdot y), allowing transfromation of the primal problem into its dual for solution.

Application to Sequence Operations

Given a sequence, each operation is assigned an index set (I_t) for (t = 1, \dots, M). Define variable (x_t) as the number of times operation (t) is repeated, relaxed to real numbers; the optimal solution remains integer.

Constraints are split into two conditions, yielding the answer:

[\min \sum_{t=1}^M x_t \quad \text{s.t.} \quad \begin{cases} \sum_{t=1}^{M} [i \in I_t] x_t \geq a_i \ -\sum_{t=1}^{M} [i \in I_t] x_t \geq -a_i \ x_t \geq 0 \end{cases}]

Taking the dual, we have:

[\max \sum_{i=1}^n a_i (p_i - q_i) \quad \text{s.t.} \quad \begin{cases} \sum_{i=1}^{n} [i \in I_t] (p_i - q_i) \leq 1 \ p_i, q_i \geq 0 \end{cases}]

Let (y_i = p_i - q_i), which can be any real number, simplifying to:

[\max \sum_{i=1}^n a_i y_i \quad \text{s.t.} \quad \sum_{i=1}^{n} [i \in I_t] y_i \leq 1]

This matrix is totally unimodular, ensuring the LP has integer vertices and thus integer solutions. The problem reduces to assigning weights (y_i) such that for each operation, the sum of weights over its indices is at most 1.

Dynamic Programming Sollution

A classic approach similar to maximum subarray sum uses DP with three suffix sums (x,y,z) representing the maximum values after three operations, constrained by (x,y,z \leq 1). If any value drops below 0, it is "truncated" by starting a new suffix. This implies (y_i) only meaningfully takes valuees (0,1,-1); values less than -1 are truncated and not optimal since -1 is never beneficial.

Time complexity is (O(n)) with a constant factor of 24.

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

long long readLong() {
    long long val = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    do {
        val = val * 10 + (ch - '0');
        ch = getchar();
    } while (ch >= '0' && ch <= '9');
    return val;
}

const int MAX_N = 100005;
const long long NEG_INF = LLONG_MIN / 2;
int seqLen;
long long arr[MAX_N];
long long dp[MAX_N][2][2][2];

void compute() {
    seqLen = readLong();
    for (int idx = 1; idx <= seqLen; ++idx) arr[idx] = readLong();
    for (int idx = 1; idx <= seqLen; ++idx)
        for (int a = 0; a < 2; ++a)
            for (int b = 0; b < 2; ++b)
                for (int c = 0; c < 2; ++c)
                    dp[idx][a][b][c] = NEG_INF;
    dp[0][0][0][0] = 0;
    for (int pos = 1; pos <= seqLen; ++pos) {
        for (int a = 0; a < 2; ++a) {
            for (int b = 0; b < 2; ++b) {
                for (int c = 0; c < 2; ++c) {
                    for (int delta = -1; delta <= 1; ++delta) {
                        if (a + delta > 1 || b + delta > 1) continue;
                        long long &curr = dp[pos][max(a + delta, 0)][c][max(b + delta, 0)];
                        curr = max(curr, dp[pos - 1][a][b][c] + delta * arr[pos]);
                    }
                }
            }
        }
    }
    long long best = 0;
    for (int a = 0; a < 2; ++a)
        for (int b = 0; b < 2; ++b)
            for (int c = 0; c < 2; ++c)
                best = max(best, dp[seqLen][a][b][c]);
    printf("%lld\n", best);
}

int main() {
    int testCases = readLong();
    while (testCases--) compute();
    return 0;
}

Greedy Algorithm

An alternative greedy method processes the sequence with variables tracking contributions.

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

long long readLong() {
    long long val = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    do {
        val = val * 10 + (ch - '0');
        ch = getchar();
    } while (ch >= '0' && ch <= '9');
    return val;
}

void greedySolve() {
    int n = readLong();
    long long contribA = 0, contribB = 0, contribC = 0;
    long long total = 0, prev = readLong();
    for (int i = 2; i <= n + 1; ++i) {
        long long curr = 0;
        if (i <= n) curr = readLong();
        long long adjust = 0;
        if (curr < contribA + contribB) {
            adjust = contribA + contribB - curr;
            if (contribA < adjust) contribB -= adjust - contribA, adjust = contribA;
            if (contribB < adjust) contribA -= adjust - contribB, adjust = contribB;
            contribA -= adjust; contribB -= adjust; curr -= adjust;
        }
        curr -= contribA + contribB;
        long long minVal = min(prev, curr);
        total += minVal; prev -= minVal; curr -= minVal; contribA += minVal;
        total += prev; contribC += prev;
        curr += adjust; total -= adjust;
        prev = curr;
        swap(contribB, contribC);
    }
    printf("%lld\n", total);
}

int main() {
    int testCases = readLong();
    while (testCases--) greedySolve();
    return 0;
}