// Árbol binario de búsqueda óptimo: los greedy que fallan, la tabla y el árbol que sale.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "interval_dp.h"

namespace {

void show(const std::vector<std::string>& names, const std::vector<long long>& f) {
    const int n = static_cast<int>(f.size());
    std::cout << "Claves y frecuencias:";
    for (int i = 0; i < n; i++) std::cout << ' ' << names[i] << '=' << f[i];
    const BstTables t = optimal_bst(f);
    std::cout << "\n  C[i][j], rango [i, j)\n  i\\j";
    for (int j = 0; j <= n; j++) std::cout << std::setw(5) << j;
    std::cout << '\n';
    for (int i = 0; i <= n; i++) {
        std::cout << std::setw(5) << i;
        for (int j = 0; j <= n; j++) {
            if (j < i) {
                std::cout << std::setw(5) << ".";
            } else {
                std::cout << std::setw(5) << t.cost[i][j];
            }
        }
        std::cout << '\n';
    }
    std::cout << "  raíz[i][j]\n  i\\j";
    for (int j = 1; j <= n; j++) std::cout << std::setw(5) << j;
    std::cout << '\n';
    for (int i = 0; i < n; i++) {
        std::cout << std::setw(5) << i;
        for (int j = 1; j <= n; j++) {
            std::cout << std::setw(5) << (j <= i ? std::string(".") : names[t.root[i][j]]);
        }
        std::cout << '\n';
    }
    std::vector<int> depth(f.size(), 0);
    bst_depths(t.root, 0, n, 1, depth);
    std::cout << "  árbol: " << bst_shape(t.root, names, 0, n) << "\n  profundidades:";
    for (int i = 0; i < n; i++) std::cout << ' ' << names[i] << '=' << depth[i];
    std::cout << "\n  costo con la definición: " << cost_from_depths(f, depth) << '\n';
    std::cout << "  por fuerza bruta: " << bst_brute(f) << '\n';
    std::cout << "  la más frecuente a la raíz: " << bst_most_frequent_root(f, 0, n, 1) << '\n';
    std::cout << "  balanceado: " << bst_balanced(f, 0, n, 1) << '\n';
}

}  // namespace

int main() {
    show({"A", "B", "C", "D"}, {2, 1, 3, 4});
}

// Mide la tabla de la cadena de matrices. Menor de 3 intentos, con -O2.
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

#include "interval_dp.h"

int main() {
    std::puts("Cadena de matrices, dimensiones al azar entre 1 y 50, menor de 3 intentos");
    std::puts("    n   combinaciones        ms");
    double previous = 0;
    for (int n : {200, 400, 800, 1600}) {
        std::mt19937 rng(11);
        std::vector<long long> d(static_cast<std::size_t>(n) + 1);
        for (long long& x : d) x = 1 + static_cast<long long>(rng() % 50);
        double best = 1e18;
        long long combinations = 0;
        for (int attempt = 0; attempt < 3; attempt++) {
            combinations = 0;
            const auto start = std::chrono::steady_clock::now();
            matrix_chain(d, &combinations);
            const auto stop = std::chrono::steady_clock::now();
            best = std::min(best, std::chrono::duration<double, std::milli>(stop - start).count());
        }
        if (previous > 0) {
            std::printf("%5d %15lld %9.1f   x%.1f\n", n, combinations, best, best / previous);
        } else {
            std::printf("%5d %15lld %9.1f\n", n, combinations, best);
        }
        previous = best;
    }
}

// Cadena de matrices: la pregunta de repaso, el greedy que falla, la tabla por largo y el orden ingenuo.
#include <iomanip>
#include <iostream>
#include <vector>

#include "interval_dp.h"

namespace {

void print_dimensions(const std::vector<long long>& d) {
    for (std::size_t i = 0; i + 1 < d.size(); i++) {
        std::cout << (i ? ", " : "") << d[i] << "x" << d[i + 1];
    }
}

void print_table(const CostTable& cost) {
    const int n = static_cast<int>(cost.size());
    std::cout << "  i\\j";
    for (int j = 0; j < n; j++) std::cout << std::setw(8) << j;
    std::cout << '\n';
    for (int i = 0; i < n; i++) {
        std::cout << std::setw(5) << i;
        for (int j = 0; j < n; j++) {
            if (j < i) {
                std::cout << std::setw(8) << ".";
            } else {
                std::cout << std::setw(8) << cost[i][j];
            }
        }
        std::cout << '\n';
    }
}

void show_chain(const std::vector<long long>& d) {
    std::cout << "Matrices: ";
    print_dimensions(d);
    const ChainTables t = matrix_chain(d);
    const int last = static_cast<int>(d.size()) - 2;
    std::cout << '\n';
    print_table(t.cost);
    std::cout << "Mínimo: " << t.cost[0][last] << ", con " << parenthesize(t.split, 0, last) << '\n';
}

}  // namespace

int main() {
    const std::vector<long long> review = {10, 30, 5, 60};
    show_chain(review);
    std::cout << "  (A0 A1) A2: " << 10 * 30 * 5 + 10 * 5 * 60 << '\n';
    std::cout << "  A0 (A1 A2): " << 30 * 5 * 60 + 10 * 30 * 60 << "\n\n";

    const std::vector<long long> greedy_case = {4, 1, 3, 5};
    std::cout << "Primero la multiplicación más barata\n  matrices: ";
    print_dimensions(greedy_case);
    std::cout << "\n  greedy: " << chain_cheapest_first(greedy_case) << ", óptimo por fuerza bruta: "
              << chain_brute(greedy_case) << "\n\n";

    const std::vector<long long> d = {10, 20, 5, 30, 2};
    show_chain(d);
    std::cout << "Por fuerza bruta: " << chain_brute(d) << "\n\n";

    std::cout << "Orden ingenuo: i de menor a mayor, j de menor a mayor, con la tabla en ceros\n";
    for (const std::vector<long long>& instance : {review, d}) {
        const NaiveOrderRun run = matrix_chain_naive_order(instance);
        std::cout << "  ";
        print_dimensions(instance);
        std::cout << '\n';
        for (const std::string& line : run.first_reads) std::cout << "    " << line << '\n';
        std::cout << "    lecturas vacías: " << run.empty_reads << ", respuesta: " << run.answer << ", correcta: "
                  << matrix_chain(instance).cost[0][instance.size() - 2] << '\n';
    }

    std::cout << "\nOtro orden válido, i de mayor a menor y j de menor a mayor: " << matrix_chain_i_descending(d) << '\n';

    long long combinations = 0;
    const std::vector<long long> ten(11, 2);
    matrix_chain(ten, &combinations);
    std::cout << "Con n = 10 matrices, combinaciones (i, k, j) probadas: " << combinations << '\n';
}

// El grafo de subproblemas, y el camino más largo en un DAG con pesos negativos y un nodo sin alcanzar.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "dag_dp.h"

namespace {

void show_subproblem_graphs() {
    std::cout << "Fibonacci, n = 5: quién lee a quién\n";
    for (int n = 2; n <= 5; n++) {
        std::cout << "  F(" << n - 1 << ") -> F(" << n << ")   F(" << n - 2 << ") -> F(" << n << ")\n";
    }
    std::cout << "  6 nodos, 8 aristas\n\n";

    const std::string a = "casa";
    const std::string b = "cosas";
    const WeightedDag g = edit_subproblem_dag(a, b);
    std::size_t arcs = 0;
    for (const auto& out : g) arcs += out.size();
    std::cout << "Distancia de edición, " << a << " -> " << b << ": " << g.size() << " nodos, " << arcs << " aristas\n";
    const LongestPaths paths = longest_paths(g, edit_node(0, 0, b.size()));
    const int target = edit_node(a.size(), b.size(), b.size());
    std::cout << "  distancia, como camino en ese DAG: " << -paths.length[target] << '\n';
    std::cout << "  el camino, en casillas (i, j):";
    for (int v : path_to(paths, target)) {
        std::cout << " (" << v / static_cast<int>(b.size() + 1) << "," << v % static_cast<int>(b.size() + 1) << ")";
    }
    std::cout << "\n\n";

    const std::vector<KnapsackObject> objects = {{2, 3}, {3, 4}, {4, 5}, {5, 8}};
    std::cout << "Mochila de la semana 7, capacidad 9, como camino más largo: " << knapsack_as_path(objects, 9) << "\n\n";
}

void show_longest_path() {
    // El nodo 0 no se alcanza desde el origen 1, y es la cola de una arista muy pesada.
    WeightedDag g(7);
    g[0] = {{2, 100}, {6, 1}};
    g[1] = {{2, 3}, {3, 5}};
    g[2] = {{4, -1}};
    g[3] = {{4, -4}, {5, 2}};
    g[4] = {{5, 6}};

    std::cout << "DAG:";
    for (int u = 0; u < 7; u++) {
        for (const Arc& arc : g[u]) std::cout << ' ' << u << "->" << arc.to << '(' << arc.weight << ')';
    }
    std::cout << "\nOrigen: 1\nOrden topológico:";
    for (int u : topological_order(g)) std::cout << ' ' << u;
    std::cout << "\n\n";

    const int source = 1;
    const LongestPaths r = longest_paths(g, source);
    const std::vector<long long> anywhere = longest_from_anywhere(g);
    std::cout << "nodo   L(v)  pred  todos en 0\n";
    for (int v = 0; v < 7; v++) {
        std::cout << std::setw(4) << v;
        if (r.reached[v]) {
            std::cout << std::setw(7) << r.length[v] << std::setw(6) << r.pred[v];
        } else {
            std::cout << std::setw(7) << "-inf" << std::setw(6) << "-";
        }
        std::cout << std::setw(12) << anywhere[v] << '\n';
    }

    std::cout << "\nCamino más largo de 1 a 5:";
    for (int v : path_to(r, 5)) std::cout << ' ' << v;
    std::cout << ", largo " << r.length[5] << '\n';

    long long total = 0;
    std::vector<int> walk;
    heaviest_arc_walk(g, source, 5, total, walk);
    std::cout << "Salir por la arista más pesada:";
    for (int v : walk) std::cout << ' ' << v;
    std::cout << ", largo " << total << '\n';
}

}  // namespace

int main() {
    show_subproblem_graphs();
    show_longest_path();
}

// Camino más largo en un DAG, y los subproblemas de la semana 7 vistos como caminos.
#pragma once

#include <algorithm>
#include <string>
#include <vector>

struct Arc {
    int to;
    long long weight;
};

using WeightedDag = std::vector<std::vector<Arc>>;

// Orden topológico por DFS, como en la semana 6: lo que termina último va primero.
inline void visit_for_order(const WeightedDag& g, int u, std::vector<char>& seen, std::vector<int>& finished) {
    seen[u] = 1;
    for (const Arc& arc : g[u]) {
        if (!seen[arc.to]) visit_for_order(g, arc.to, seen, finished);
    }
    finished.push_back(u);
}

inline std::vector<int> topological_order(const WeightedDag& g) {
    std::vector<char> seen(g.size(), 0);
    std::vector<int> finished;
    for (int u = 0; u < static_cast<int>(g.size()); u++) {
        if (!seen[u]) visit_for_order(g, u, seen, finished);
    }
    std::reverse(finished.begin(), finished.end());
    return finished;
}

struct LongestPaths {
    std::vector<long long> length;  // solo tiene sentido si reached[v]
    std::vector<char> reached;      // hay camino desde el origen
    std::vector<int> pred;          // nodo anterior en un camino más largo, o -1
};

// Invariante: al llegar a u en el orden, ya se miraron todas las aristas que entran a u, así que
// length[u] es definitivo. De un nodo no alcanzado no se sale: no hay valor que sumarle.
inline LongestPaths longest_paths(const WeightedDag& g, int source) {
    const std::size_t n = g.size();
    LongestPaths r{std::vector<long long>(n, 0), std::vector<char>(n, 0), std::vector<int>(n, -1)};
    r.reached[source] = 1;
    for (int u : topological_order(g)) {
        if (!r.reached[u]) continue;
        for (const Arc& arc : g[u]) {
            const long long candidate = r.length[u] + arc.weight;
            if (!r.reached[arc.to] || candidate > r.length[arc.to]) {
                r.reached[arc.to] = 1;
                r.length[arc.to] = candidate;
                r.pred[arc.to] = u;
            }
        }
    }
    return r;
}

inline std::vector<int> path_to(const LongestPaths& r, int target) {
    std::vector<int> path;
    for (int v = target; v != -1; v = r.pred[v]) path.push_back(v);
    std::reverse(path.begin(), path.end());
    return path;
}

// Error: todos empiezan en 0, como si cualquier nodo fuera origen.
inline std::vector<long long> longest_from_anywhere(const WeightedDag& g) {
    std::vector<long long> length(g.size(), 0);
    for (int u : topological_order(g)) {
        for (const Arc& arc : g[u]) length[arc.to] = std::max(length[arc.to], length[u] + arc.weight);
    }
    return length;
}

// Greedy que falla: salir siempre por la arista de mayor peso. Devuelve el largo del recorrido
// si llega al destino, y escribe el recorrido en walk.
inline bool heaviest_arc_walk(const WeightedDag& g, int source, int target, long long& total, std::vector<int>& walk) {
    total = 0;
    walk = {source};
    int u = source;
    while (u != target && !g[u].empty()) {
        const Arc* best = &g[u][0];
        for (const Arc& arc : g[u]) {
            if (arc.weight > best->weight) best = &arc;
        }
        total += best->weight;
        u = best->to;
        walk.push_back(u);
    }
    return u == target;
}

// Árbitro: prueba todos los caminos desde u. Máximo en best[v] para cada v alcanzable.
inline void all_paths(const WeightedDag& g, int u, long long so_far, std::vector<long long>& best,
                      std::vector<char>& seen) {
    if (!seen[u] || so_far > best[u]) {
        seen[u] = 1;
        best[u] = so_far;
    }
    for (const Arc& arc : g[u]) all_paths(g, arc.to, so_far + arc.weight, best, seen);
}

// El grafo de subproblemas de la distancia de edición: una arista por cada casilla leída, de la
// casilla leída a la que la lee. El peso es menos el costo, para usar el camino más largo.
inline int edit_node(std::size_t i, std::size_t j, std::size_t m) {
    return static_cast<int>(i * (m + 1) + j);
}

inline WeightedDag edit_subproblem_dag(const std::string& a, const std::string& b) {
    const std::size_t n = a.size();
    const std::size_t m = b.size();
    WeightedDag g((n + 1) * (m + 1));
    for (std::size_t i = 0; i <= n; i++) {
        for (std::size_t j = 0; j <= m; j++) {
            const int here = edit_node(i, j, m);
            if (i < n) g[here].push_back({edit_node(i + 1, j, m), -1});
            if (j < m) g[here].push_back({edit_node(i, j + 1, m), -1});
            if (i < n && j < m) g[here].push_back({edit_node(i + 1, j + 1, m), a[i] == b[j] ? 0 : -1});
        }
    }
    return g;
}

// El de la mochila: un nodo por (i, c), más un origen que da a todas las casillas (0, c).
struct KnapsackObject {
    std::size_t weight;
    long long value;
};

inline long long knapsack_as_path(const std::vector<KnapsackObject>& objects, std::size_t capacity) {
    const std::size_t rows = objects.size() + 1;
    const std::size_t columns = capacity + 1;
    const auto node = [columns](std::size_t i, std::size_t c) { return static_cast<int>(i * columns + c); };
    const int source = static_cast<int>(rows * columns);
    WeightedDag g(rows * columns + 1);
    for (std::size_t c = 0; c < columns; c++) g[source].push_back({node(0, c), 0});
    for (std::size_t i = 1; i < rows; i++) {
        const KnapsackObject& object = objects[i - 1];
        for (std::size_t c = 0; c < columns; c++) {
            g[node(i - 1, c)].push_back({node(i, c), 0});
            if (object.weight <= c) g[node(i - 1, c - object.weight)].push_back({node(i, c), object.value});
        }
    }
    return longest_paths(g, source).length[node(rows - 1, capacity)];
}

// Una cadena de n nodos, primero sin recursión y luego con ella: deep_chain N. Se compila con -O2.
#include <cstdlib>
#include <iostream>
#include <vector>

#include "tree_dp.h"

int main(int argc, char* argv[]) {
    const int n = argc > 1 ? std::atoi(argv[1]) : 100000;
    RootedTree chain{std::vector<std::vector<int>>(static_cast<std::size_t>(n)), 0,
                     std::vector<long long>(static_cast<std::size_t>(n), 1)};
    for (int v = 0; v + 1 < n; v++) chain.children[v].push_back(v + 1);
    std::cout << "orden inverso de BFS, nodos bajo la raíz: " << subtree_sizes_bfs_order(chain.children, 0)[0] << std::endl;
    std::cout << "recursión, conjunto independiente: " << independent_set_value(chain) << std::endl;
}

// Programación dinámica sobre intervalos: cadena de matrices y árbol binario de búsqueda óptimo.
#pragma once

#include <algorithm>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>

using CostTable = std::vector<std::vector<long long>>;
using SplitTable = std::vector<std::vector<int>>;

constexpr long long NO_COST = std::numeric_limits<long long>::max();

// ---------- Cadena de matrices. La matriz i mide d[i] x d[i + 1]. ----------

struct ChainTables {
    CostTable cost;    // cost[i][j]: el mínimo para multiplicar las matrices i..j, ambas incluidas
    SplitTable split;  // split[i][j]: la k de la última multiplicación
};

inline long long merge_cost(const std::vector<long long>& d, int i, int k, int j) {
    return d[i] * d[k + 1] * d[j + 1];
}

// Por largo creciente: todo lo que se lee es más corto que lo que se escribe.
inline ChainTables matrix_chain(const std::vector<long long>& d, long long* combinations = nullptr) {
    const int n = static_cast<int>(d.size()) - 1;
    ChainTables t{CostTable(n, std::vector<long long>(n, 0)), SplitTable(n, std::vector<int>(n, -1))};
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i + length - 1 < n; i++) {
            const int j = i + length - 1;
            t.cost[i][j] = NO_COST;
            for (int k = i; k < j; k++) {
                if (combinations) (*combinations)++;
                const long long c = t.cost[i][k] + t.cost[k + 1][j] + merge_cost(d, i, k, j);
                if (c < t.cost[i][j]) {
                    t.cost[i][j] = c;
                    t.split[i][j] = k;
                }
            }
        }
    }
    return t;
}

// También sirve: i de mayor a menor y j de menor a mayor. Lo leído tiene i mayor, o j menor.
inline long long matrix_chain_i_descending(const std::vector<long long>& d) {
    const int n = static_cast<int>(d.size()) - 1;
    CostTable cost(n, std::vector<long long>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            cost[i][j] = NO_COST;
            for (int k = i; k < j; k++) {
                cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k + 1][j] + merge_cost(d, i, k, j));
            }
        }
    }
    return n == 0 ? 0 : cost[0][n - 1];
}

// Error: i de menor a mayor y j de menor a mayor. Las casillas sin llenar valen 0 y se leen igual.
struct NaiveOrderRun {
    long long answer;
    long long empty_reads;
    std::vector<std::string> first_reads;
};

inline NaiveOrderRun matrix_chain_naive_order(const std::vector<long long>& d) {
    const int n = static_cast<int>(d.size()) - 1;
    CostTable cost(n, std::vector<long long>(n, 0));
    std::vector<std::vector<char>> filled(n, std::vector<char>(n, 0));
    for (int i = 0; i < n; i++) filled[i][i] = 1;
    NaiveOrderRun run{0, 0, {}};
    const auto read = [&](int writing_i, int writing_j, int i, int j) {
        if (!filled[i][j]) {
            run.empty_reads++;
            run.first_reads.push_back("M[" + std::to_string(writing_i) + "][" + std::to_string(writing_j) +
                                      "] lee M[" + std::to_string(i) + "][" + std::to_string(j) + "], vacía");
        }
        return cost[i][j];
    };
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long best = NO_COST;
            for (int k = i; k < j; k++) {
                best = std::min(best, read(i, j, i, k) + read(i, j, k + 1, j) + merge_cost(d, i, k, j));
            }
            cost[i][j] = best;
            filled[i][j] = 1;
        }
    }
    run.answer = n == 0 ? 0 : cost[0][n - 1];
    return run;
}

inline std::string parenthesize(const SplitTable& split, int i, int j) {
    if (i == j) return "A" + std::to_string(i);
    const int k = split[i][j];
    return "(" + parenthesize(split, i, k) + " " + parenthesize(split, k + 1, j) + ")";
}

// Árbitro: arma cada parentización y calcula su costo multiplicando de verdad las dimensiones.
struct ChainPlan {
    long long rows;
    long long columns;
    long long cost;
};

inline std::vector<ChainPlan> all_chain_plans(const std::vector<long long>& d, int i, int j) {
    if (i == j) return {{d[i], d[i + 1], 0}};
    std::vector<ChainPlan> plans;
    for (int k = i; k < j; k++) {
        for (const ChainPlan& left : all_chain_plans(d, i, k)) {
            for (const ChainPlan& right : all_chain_plans(d, k + 1, j)) {
                plans.push_back({left.rows, right.columns,
                                 left.cost + right.cost + left.rows * left.columns * right.columns});
            }
        }
    }
    return plans;
}

inline long long chain_brute(const std::vector<long long>& d) {
    long long best = NO_COST;
    for (const ChainPlan& plan : all_chain_plans(d, 0, static_cast<int>(d.size()) - 2)) {
        best = std::min(best, plan.cost);
    }
    return best;
}

// Greedy que falla: hacer siempre primero la multiplicación vecina más barata.
inline long long chain_cheapest_first(std::vector<long long> d) {
    long long total = 0;
    while (d.size() > 2) {
        std::size_t best = 1;
        for (std::size_t m = 1; m + 1 < d.size(); m++) {
            if (d[m - 1] * d[m] * d[m + 1] < d[best - 1] * d[best] * d[best + 1]) best = m;
        }
        total += d[best - 1] * d[best] * d[best + 1];
        d.erase(d.begin() + static_cast<std::ptrdiff_t>(best));
    }
    return total;
}

// ---------- Árbol binario de búsqueda óptimo. Rangos semiabiertos [i, j). ----------

struct BstTables {
    CostTable cost;  // cost[i][j]: el mínimo de la suma de frecuencia por profundidad, claves i..j-1
    SplitTable root; // root[i][j]: la clave que va en la raíz de ese rango
};

inline std::vector<long long> prefix_sums(const std::vector<long long>& f) {
    std::vector<long long> sum(f.size() + 1, 0);
    for (std::size_t i = 0; i < f.size(); i++) sum[i + 1] = sum[i] + f[i];
    return sum;
}

inline BstTables optimal_bst(const std::vector<long long>& f) {
    const int n = static_cast<int>(f.size());
    const std::vector<long long> sum = prefix_sums(f);
    BstTables t{CostTable(n + 1, std::vector<long long>(n + 1, 0)), SplitTable(n + 1, std::vector<int>(n + 1, -1))};
    for (int length = 1; length <= n; length++) {
        for (int i = 0; i + length <= n; i++) {
            const int j = i + length;
            long long best = NO_COST;
            for (int r = i; r < j; r++) {
                const long long c = t.cost[i][r] + t.cost[r + 1][j];
                if (c < best) {
                    best = c;
                    t.root[i][j] = r;
                }
            }
            t.cost[i][j] = best + sum[j] - sum[i];
        }
    }
    return t;
}

// Las profundidades de cada clave en el árbol que dice la tabla. La raíz tiene profundidad 1.
inline void bst_depths(const SplitTable& root, int i, int j, int depth, std::vector<int>& out) {
    if (i >= j) return;
    const int r = root[i][j];
    out[r] = depth;
    bst_depths(root, i, r, depth + 1, out);
    bst_depths(root, r + 1, j, depth + 1, out);
}

inline long long cost_from_depths(const std::vector<long long>& f, const std::vector<int>& depth) {
    long long total = 0;
    for (std::size_t i = 0; i < f.size(); i++) total += f[i] * depth[i];
    return total;
}

inline std::string bst_shape(const SplitTable& root, const std::vector<std::string>& names, int i, int j) {
    if (i >= j) return "-";
    const int r = root[i][j];
    if (j - i == 1) return names[r];
    return names[r] + "(" + bst_shape(root, names, i, r) + " " + bst_shape(root, names, r + 1, j) + ")";
}

// Árbitro: genera todos los árboles del rango como listas de profundidades, y mide con la definición.
inline std::vector<std::vector<int>> all_bst_depths(int i, int j, int n) {
    if (i >= j) return {std::vector<int>(n, 0)};
    std::vector<std::vector<int>> trees;
    for (int r = i; r < j; r++) {
        for (const std::vector<int>& left : all_bst_depths(i, r, n)) {
            for (const std::vector<int>& right : all_bst_depths(r + 1, j, n)) {
                std::vector<int> depth(n, 0);
                depth[r] = 1;
                for (int x = i; x < r; x++) depth[x] = left[x] + 1;
                for (int x = r + 1; x < j; x++) depth[x] = right[x] + 1;
                trees.push_back(depth);
            }
        }
    }
    return trees;
}

inline long long bst_brute(const std::vector<long long>& f) {
    const int n = static_cast<int>(f.size());
    long long best = NO_COST;
    for (const std::vector<int>& depth : all_bst_depths(0, n, n)) {
        best = std::min(best, cost_from_depths(f, depth));
    }
    return best;
}

// Greedy que falla: la clave más frecuente a la raíz, y lo mismo en cada lado.
inline long long bst_most_frequent_root(const std::vector<long long>& f, int i, int j, int depth) {
    if (i >= j) return 0;
    int r = i;
    for (int x = i; x < j; x++) {
        if (f[x] > f[r]) r = x;
    }
    return f[r] * depth + bst_most_frequent_root(f, i, r, depth + 1) + bst_most_frequent_root(f, r + 1, j, depth + 1);
}

// La otra idea natural: el árbol balanceado, ignorando las frecuencias.
inline long long bst_balanced(const std::vector<long long>& f, int i, int j, int depth) {
    if (i >= j) return 0;
    const int r = i + (j - i) / 2;
    return f[r] * depth + bst_balanced(f, i, r, depth + 1) + bst_balanced(f, r + 1, j, depth + 1);
}

// Mide las dos versiones de la subsecuencia creciente más larga. Menor de 3 intentos, con -O2.
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

#include "lis.h"

namespace {

std::vector<int> random_values(std::size_t n, unsigned seed) {
    std::mt19937 rng(seed);
    std::vector<int> a(n);
    for (int& x : a) x = static_cast<int>(rng() >> 2);
    return a;
}

template <typename Function>
double best_ms(Function run) {
    double best = 1e18;
    for (int attempt = 0; attempt < 3; attempt++) {
        const auto start = std::chrono::steady_clock::now();
        run();
        const auto stop = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(stop - start).count());
    }
    return best;
}

}  // namespace

int main() {
    std::puts("Subsecuencia creciente más larga, valores al azar, menor de 3 intentos");
    std::puts("        n   largo   tabla ms   finales ms");
    for (std::size_t n : {10000u, 20000u, 40000u, 80000u, 1000000u, 2000000u, 4000000u}) {
        const std::vector<int> a = random_values(n, 9);
        std::size_t length = 0;
        const double fast = best_ms([&] { length = lis_length_tails(a); });
        if (n <= 80000u) {
            int slow_length = 0;
            const double slow = best_ms([&] { slow_length = lis_length_quadratic(a); });
            if (slow_length != static_cast<int>(length)) return 1;
            std::printf("%9zu %7zu %10.1f %12.1f\n", n, length, slow, fast);
        } else {
            std::printf("%9zu %7zu %10s %12.1f\n", n, length, "-", fast);
        }
    }
}

// Subsecuencia creciente más larga: la tabla, el arreglo de finales paso a paso y la reconstrucción.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "lis.h"

namespace {

void print_values(const std::vector<int>& a) {
    for (std::size_t i = 0; i < a.size(); i++) std::cout << (i ? " " : "") << a[i];
}

void show_quadratic(const std::vector<int>& a) {
    const LisTable t = lis_quadratic(a);
    std::cout << "   i:";
    for (std::size_t i = 0; i < a.size(); i++) std::cout << std::setw(3) << i;
    std::cout << "\na[i]:";
    for (int x : a) std::cout << std::setw(3) << x;
    std::cout << "\nE[i]:";
    for (int e : t.ending) std::cout << std::setw(3) << e;
    std::cout << "\npred:";
    for (int p : t.pred) std::cout << std::setw(3) << p;
    std::cout << '\n';
}

void show_tails(const std::vector<int>& a) {
    std::vector<int> tails;
    std::vector<int> tail_index;
    std::vector<int> pred(a.size(), -1);
    std::cout << " i  x  posición  finales después        índices    pred[i]\n";
    for (int i = 0; i < static_cast<int>(a.size()); i++) {
        const auto it = std::lower_bound(tails.begin(), tails.end(), a[i]);
        const std::size_t position = static_cast<std::size_t>(it - tails.begin());
        if (position > 0) pred[i] = tail_index[position - 1];
        if (it == tails.end()) {
            tails.push_back(a[i]);
            tail_index.push_back(i);
        } else {
            *it = a[i];
            tail_index[position] = i;
        }
        std::cout << std::setw(2) << i << std::setw(3) << a[i] << std::setw(10) << position << "  ";
        std::string text;
        for (int x : tails) text += std::to_string(x) + " ";
        std::cout << std::left << std::setw(23) << text;
        text.clear();
        for (int x : tail_index) text += std::to_string(x) + " ";
        std::cout << std::setw(11) << text << std::right << std::setw(4) << pred[i] << '\n';
    }
}

}  // namespace

int main() {
    const std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    std::cout << "Arreglo: ";
    print_values(a);
    std::cout << "\n\nLa tabla cuadrática\n";
    show_quadratic(a);
    std::cout << "Largo: " << lis_length_quadratic(a) << "\nCon pred, desde la primera casilla con ese largo:";
    {
        const LisTable t = lis_quadratic(a);
        std::vector<int> walk;
        for (int i = static_cast<int>(std::max_element(t.ending.begin(), t.ending.end()) - t.ending.begin()); i != -1; i = t.pred[i]) {
            walk.push_back(a[i]);
        }
        for (std::size_t k = walk.size(); k-- > 0;) std::cout << ' ' << walk[k];
    }
    std::cout << "\n\nEl arreglo de finales, con lower_bound\n";
    show_tails(a);
    std::cout << "Largo: " << lis_length_tails(a) << "\nReconstruida:";
    for (int i : lis_indices(a)) std::cout << ' ' << a[i];

    std::cout << "\n\nTomar todo lo que sea mayor que lo último tomado\n";
    for (const std::vector<int>& b : {std::vector<int>{5, 1, 2, 3}, std::vector<int>{1, 7, 2, 3, 4}}) {
        std::cout << "  ";
        print_values(b);
        std::cout << ": greedy " << lis_greedy_take(b) << ", óptimo " << lis_length_tails(b) << '\n';
    }

    const std::vector<int> c = {2, 5, 3, 7, 1};
    std::cout << "\nLos finales no son una subsecuencia\n  arreglo: ";
    print_values(c);
    std::cout << "\n  finales: ";
    print_values(final_tails(c));
    std::cout << "\n  reconstruida:";
    for (int i : lis_indices(c)) std::cout << ' ' << c[i];
    std::cout << '\n';

    std::cout << "\nlower_bound y upper_bound\n";
    for (const std::vector<int>& d : {std::vector<int>{2, 2, 2}, std::vector<int>{1, 3, 3, 5}}) {
        std::cout << "  ";
        print_values(d);
        std::cout << ": con lower_bound " << lis_length_tails(d) << ", con upper_bound "
                  << non_decreasing_length_tails(d) << '\n';
    }
}