题解归档 - cf2165A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2165A
• 本地来源：problems/cf2165A/idea.md
• 题目链接：https://codeforces.com/contest/2165/problem/A
• 原始标题：cf2165A Cyclic Merging

思路

cf2165A Cyclic Merging

Pattern

Optimization / exchange argument / Cartesian tree.

Claim

For a linear array, the minimum merge cost is the sum of the parent values in its max Cartesian tree, over all non-root nodes.

For the ring, cut the cycle at any occurrence of the global maximum and solve the resulting linear instance. Equal maxima give the same value with the stable Cartesian-tree tie rule used in the code.

Necessary

Every merge tree over a linear order has an internal node for each merged interval. The cost of an internal node is the maximum value inside that interval. Since the interval maximum is independent of the split, the optimal recurrence is:

dp[l][r] = max(a[l..r]) + min(dp[l][k] + dp[k+1][r]).

The Cartesian tree is the compact form of this recurrence: each non-root leaf/subtree is first joined through the nearest dominating maximum, contributing exactly its parent value.

Sufficient

Build the max Cartesian tree after cutting at a global maximum. Merging bottom-up according to the tree is a legal adjacent-merge order and pays exactly the parent-value sum.

Brute / Check

Checked by exhaustive DP over all cyclic merge choices for n <= 7, small values, against the implemented formula.

Edge

• n=2
• zeros
• repeated global maximum
• all values equal

代码

来源：problems/cf2165A/solution.cpp

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

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

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

        int root = 0;
        for (int i = 1; i < n; i++) {
            if (a[i] > a[root]) root = i;
        }

        vector<ll> b(n);
        for (int i = 0; i < n; i++) b[i] = a[(root + i) % n];

        vector<int> par(n, -1), st;
        st.reserve(n);
        for (int i = 0; i < n; i++) {
            int last = -1;
            while (!st.empty() && b[st.back()] < b[i]) {
                last = st.back();
                st.pop_back();
            }
            if (!st.empty()) par[i] = st.back();
            if (last != -1) par[last] = i;
            st.push_back(i);
        }

        ll ans = 0;
        for (int i = 0; i < n; i++) {
            if (par[i] != -1) ans += b[par[i]];
        }
        cout << ans << '\n';
    }
    return 0;
}