Problem Overview

Consider a linear arrangement of n sequential zones, each containing a key with a specific value. The objective is to recursively divide the entire sequence until only single zones remain. During the merging phase of these divided sections, a score is accumulated. Specifically, when a section spanning from index L to R was initially split at index K, the merge yields a score of (val[L] + val[R]) * val[K]. The goal is to determine the maximum total score achievable and output the sequence of split positions. This sequence must follow a level-order traversal (splitting stages from beginning to end, left to right within each stage). If multiple split configurations yield the maximum score, prioritize the one with the leftmost split positions.

Interval Dynamic Programming Approach

Let dp[L][R] represent the maximum score obtainable from the subarray bounded by indices L and R. For any interval containing more than one element, we must choose a split point K where L <= K < R. This division separates the interval into [L, K] and [K+1, R]. The total score for choosing K is the sum of the scores from the left sub-interval, the right sub-interval, and the score generated by the merge operation itself.

The state transition equation is formulated as:

dp[L][R] = max(dp[L][K] + dp[K+1][R] + (val[L] + val[R]) * val[K])

Simultaneously, we maintain a decision matrix opt_split[L][R] to store the optimal index K that maximizes the value for the interval [L, R]. Since we iterate through intervals of increasing length, the subproblems dp[L][K] and dp[K+1][R] are always computed before the parent interval [L, R].

Retrieving the Split Sequence

The problem requires the split points to be printed in the order they occur: first the initial split, then the splits of the resulting halves from left to right, and so on. This corresponds directly to a breadth-first search (BFS) over the interval tree.

Starting with the full interval [1, n] in a queue, we repeatedly extract an interval [L, R], output its optimal split point opt_split[L][R], and enqueue its valid left and right sub-intervals, provided they contain more than one element. This naturally produces the required level-order output.

Complexity Analysis

• Time Complexity: O(n^3). There are O(n^2) states, and each state requires O(n) transitions to evaluate all possible split points.
• Space Complexity: O(n^2) for storing the DP table and the split decision matrix.

Implementation

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int num_zones;
    if (!(cin >> num_zones)) return 0;

    vector<int> key_values(num_zones + 1);
    for (int i = 1; i <= num_zones; ++i) {
        cin >> key_values[i];
    }

    // dp_table[L][R] stores the max score for interval [L, R]
    vector<vector<int>> dp_table(num_zones + 1, vector<int>(num_zones + 1, 0));
    // best_cut[L][R] stores the optimal split index for interval [L, R]
    vector<vector<int>> best_cut(num_zones + 1, vector<int>(num_zones + 1, 0));

    // Iterate over interval lengths
    for (int length = 2; length <= num_zones; ++length) {
        // Iterate over starting indices
        for (int left = 1; left + length - 1 <= num_zones; ++left) {
            int right = left + length - 1;

            // Evaluate all possible split points
            for (int cut = left; cut < right; ++cut) {
                int current_score = dp_table[left][cut] + dp_table[cut + 1][right] +
                                    (key_values[left] + key_values[right]) * key_values[cut];

                if (current_score > dp_table[left][right]) {
                    dp_table[left][right] = current_score;
                    best_cut[left][right] = cut;
                }
            }
        }
    }

    cout << dp_table[1][num_zones] << "\n";

    // BFS to output split positions in level order
    queue<pair<int, int>> interval_queue;
    interval_queue.push({1, num_zones});

    while (!interval_queue.empty()) {
        auto current = interval_queue.front();
        interval_queue.pop();

        int L = current.first;
        int R = current.second;
        int cut_pos = best_cut[L][R];

        cout << cut_pos << " ";

        if (cut_pos - L >= 1) {
            interval_queue.push({L, cut_pos});
        }
        if (R - cut_pos - 1 >= 1) {
            interval_queue.push({cut_pos + 1, R});
        }
    }

    cout << "\n";
    return 0;
}