Вариация проблем с укладкой коробки

Question

Некоторое время я пытался решить следующую проблему конкурса:

Вы хотите построить башню как можно выше из N кирпичей. Каждый кирпич представляет собой кубоид с квадратным дном, а башня представляет собой набор кирпичей, сложенных друг на друге. Чтобы башня не стала нестабильной, каждый кирпич должен быть строго шире кирпича сверху. Поэтому башня построена из самых широких кирпичей в нижней части и самой узкой в ​​верхней части. По эстетическим соображениям каждый кирпич должен быть по крайней мере таким же высоким, как тот кирпич, на котором он лежит.

Нам дано количество кирпичей N, а также их ширина и высота. Мы хотим выяснить максимальную высоту.

После окончания конкурса были представлены следующие два решения:

Решение 1:

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

struct Tree {
    typedef ll T;
    const T LOW = -1234567890;
    T f(T a, T b) { return max(a, b); }

    int n;
    vi s;
    Tree() {}
    Tree(int m, T def=0) { init(m, def); }
    void init(int m, T def) {
        n = 1; while (n < m) n *= 2;
        s.assign(n + m, def);
        s.resize(2 * n, LOW);
        for (int i = n; i --> 1; )
            s[i] = f(s[i * 2], s[i*2 + 1]);
    }
    void update(int pos, T val) {
        pos += n;
        s[pos] = val;
        for (pos /= 2; pos >= 1; pos /= 2)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int l, int r) { return que(1, l, r, 0, n); }
    T que(int pos, int l, int r, int lo, int hi) {
        if (r <= lo || hi <= l) return LOW;
        if (l <= lo && hi <= r) return s[pos];
        int m = (lo + hi) / 2;
        return f(que(2 * pos, l, r, lo, m),
                que(2 * pos + 1, l, r, m, hi));
    } 
};

int main() { 
    cin.sync_with_stdio(false);
    ll n; cin>>n;
    map<ll,ll> heights;
    vector<pii> v(n);
    rep(i,0,n){
        cin>>v[i].first>>v[i].second;
        heights[v[i].second] = 1;
    }
    ll ind = 0;
    for(auto e:heights) heights[e.first] = ind++;

    sort(all(v));
    reverse(all(v));

    Tree st(n);
    rep(i,0,v.size())
        if (i == 0 || v[i] != v[i-1])
        st.update(heights[v[i].second],st.query(0,heights[v[i].second]+1) + v[i].second);
    cout<<st.query(0,n)<<endl;
}

Решение 2:

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

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    cin.sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int N;
    cin >> N;
    vector<pii> bricks;
    rep(i,0,N) {
        int w, h;
        cin >> w >> h;
        bricks.emplace_back(w, h);
    }
    sort(all(bricks));
    // width strictly increasing, height weakly decreasing
    map<int, ll> answers;
    answers[INT_MAX] = 0;
    pii lastbr = {-1, -1};
    trav(br, bricks) {
        if (br == lastbr) continue;
        lastbr = br;
        int h = br.second;
        auto it = answers.lower_bound(h);
        assert(it != answers.end());
        ll nh = it->second + h;
        if (it->first == h) {
            it->second = nh;
        } else {
            it = answers.insert(it, make_pair(h, nh));
        }
        while (it != answers.begin()) {
            --it;
            if (it->second <= nh) it = answers.erase(it);
            else break;
        }
    }

    ll res = 0;
    trav(pa, answers) res = max(res, pa.second);
    cout << res << endl;

    exit(0);
}

Я довольно новичок в соревнованиях по программированию и C++. Если бы кто-нибудь мог объяснить мне алгоритм по-новому, я был бы благодарен. Я в основном написал код на Java, поэтому, если кто-то захочет представить пример или объяснение в коде, я бы предпочел java. Заранее спасибо!

Постановка задачи полностью с примером ввода / вывода: https://translate.google.se/translate?hl=sv&sl=sv&tl=en&u=https%3A%2F%2Fpo.kattis.com%2Fproblems%2Ftornbygge

Еще одна проблема, которая, как мне показалось, выглядела аналогично: башня ящиков (укладка кубов)

Проблема с оригинальной коробкой https://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/