Se requiere apilar cajas con dimensiones (ancho, profundidad, altura) siguiendo la regla de que una caja solo puede colocares sobre otra si todas sus dimensiones son estrictamente menores. El objetivo es calcular la altura máxima posible de la pila.

1. Estrategia de programación dinámica con ordenación

La solución implica ordenar las cajas y aplicar un enfoque de programación dinámica. Existen dos variantes principales:

• Ordenar de mayor a menor: dp[i] representa la altura máxima cuando la caja i es la base
• Ordenar de menor a mayor: dp[i] representa la altura máxima cuando la caja i es la cima

class Solucion {
public:
    int calcularPila(vector<vector<int>>& cajas) {
        sort(cajas.begin(), cajas.end(), [](vector<int>& a, vector<int>& b){
            return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
        });
        int n = cajas.size();
        vector<int> dp(n);
        
        for(int i = 0; i < n; i++) {
            dp[i] = cajas[i][2];
            for(int j = 0; j < i; j++) {
                if(cajas[j][0] > cajas[i][0] && 
                   cajas[j][1] > cajas[i][1] && 
                   cajas[j][2] > cajas[i][2]) {
                    dp[i] = max(dp[i], dp[j] + cajas[i][2]);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

2. Implementación con árbol binario indexado (2D BIT)

Esta aproximación utiliza discretización y un árbol binario indexado bidimensional para optimizar la complejidad temporal:

using Triplet = tuple<int, int, int>;

class ArbolIndexado {
public:
    vector<vector<int>> estructura;
    int anchoMax, profundidadMax;
    
    ArbolIndexado(int ancho, int profundidad) {
        anchoMax = ancho;
        profundidadMax = profundidad;
        estructura.resize(ancho + 1);
        for (int i = 0; i <= ancho; i++)
            estructura[i].assign(profundidad + 1, 0);
    }

    int consultar(int w, int d) {
        int resultado = 0;
        for (int i = w; i > 0; i -= i & -i)
            for (int j = d; j > 0; j -= j & -j)
                resultado = max(resultado, estructura[i][j]);
        return resultado;
    }

    void actualizar(int w, int d, int valor) {
        for (int i = w; i <= anchoMax; i += i & -i)
            for (int j = d; j <= profundidadMax; j += j & -j)
                estructura[i][j] = max(estructura[i][j], valor);
    }
};

class Solucion {
public:
    int calcularPila(vector<vector<int>>& cajas) {
        set<int> anchos, profundidades;
        unordered_map<int, int> mapeoAncho, mapeoProfundidad;
        vector<Triplet> datos;
        
        for (auto& caja : cajas) {
            anchos.insert(caja[0]);
            profundidades.insert(caja[1]);
            datos.emplace_back(caja[2], -caja[0], -caja[1]);
        }
        
        sort(datos.begin(), datos.end());
        
        int indiceAncho = 0;
        for (int a : anchos)
            mapeoAncho[a] = ++indiceAncho;
            
        int indiceProfundidad = 0;
        for (int p : profundidades)
            mapeoProfundidad[p] = ++indiceProfundidad;
            
        ArbolIndexado arbol(indiceAncho, indiceProfundidad);
        int alturaMaxima = 0;
        
        for (auto& [altura, ancho, profundidad] : datos) {
            ancho = -ancho; profundidad = -profundidad;
            int alturaAnterior = arbol.consultar(mapeoAncho[ancho]-1, mapeoProfundidad[profundidad]-1);
            alturaMaxima = max(alturaMaxima, alturaAnterior + altura);
            arbol.actualizar(mapeoAncho[ancho], mapeoProfundidad[profundidad], alturaAnterior + altura);
        }
        return alturaMaxima;
    }
};