AOI Study Hub

Appearance

Sequence ​

Problem Statement ​

Solution ​

We start with a sequence of numbers:

We can do the following operation:

  • Pick two neighbors
  • Replace them with one number
  • Pay a cost of .

After operations, only one number remains. We want the minimum possible total cost.

The Answer ​

It turns out the answer is very simple:

Why This Works ​

We need to explain two things:

  1. Why we can’t do better than this sum (lower bound).
  2. Why we can actually achieve it (upper bound).

Step 1. Why we can’t do better ​

Think about the boundaries between elements:

Each boundary “disappears” when those two sides finally get merged.

When and are merged for the first time, we must pay

This happens once per boundary, no matter what order we pick.

👉 That means the total cost is at least

Step 2. Why this sum is achievable ​

Now we show we can actually reach this exact value.

The trick: always merge the pair with the smallest possible max (a "minimum reduce").

Why is this safe? Because:

  • If you merge that pair, the neighbors on the left and right are at least as big, so the surrounding maxima don’t change.
  • The total "sum of max’s of neighbors" decreases by exactly the cost you just paid.

So after each merge:

If you repeat this until one element is left, you’ll have paid exactly the total sum of maxima from the beginning.

Implementation ​

By Iyed Baassou.

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

typedef long long ll;

int main() {
    int n; cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    ll res = 0;

    for (int i = 1; i < n; ++i) {
        res += max(a[i], a[i - 1]);
    }

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