#include #include #define MAX_N 102400 // massimo numero di lastre che potrebbero capitarmi #define MAX_L 1024000 // massima larghezza delle lastre using namespace std; struct lastra { int x, y; // struttura per le lastre con confronto su prima coordinata bool operator<(const lastra& other) const { if (x < other.x) return true; return false; } }; lastra Lastre[MAX_N]; // vettore con l'elenco delle lastre int N; int min( int x, int y ) // funzione che calcola il minimo { return x < y ? x : y; } int max( int x, int y ) // funzione che calcola il massimo { return x > y ? x : y; } int greedy() // funzione che calcola la massima altezza possibile { // costruendo la torre dalla cima verso la base lastra Base, Seconda; // QUESTA FUNZIONE STAMPA ANCHE LA COMPOSIZIONE DELLA TORRE, int altezza; // anche se non richiesto nella specifica del problema. cout << endl; Seconda.x = 0; // parto con una torre con la prima lastra, e sopra Seconda.y = 0; // la "lastra vuota" 0x0. Base = Lastre[0]; altezza = 1; for (int i=1; i Base.y) { // se posso aggiungerla alla base la aggiungo cout << Base.x << " x " << Base.y << endl; // (e quindi la vecchia base ora e' definitiva) Seconda = Base; Base = Lastre[i]; altezza++; } // se posso sostituirla alla base la sostituisco else if (Lastre[i].y > Seconda.y) { // (tanto ci guadagno solo perche' la base si restringe) Base = Lastre[i]; } // altrimenti lascio perdere. (ATTENZIONE: per via di questo, l'algoritmo } // ogni tanto non trova la soluzione ottima. // per esempio per input pari a: // 5 // 6 4 // 7 5 // 8 1 // 9 2 // 10 3 cout << Base.x << " x " << Base.y << endl << "===================" << endl; return altezza; } int main() { int a, b; cin >> N; for (int i=0; i> a >> b; Lastre[i].x = max(a,b); // e le memorizzo "ruotandole tutte Lastre[i].y = min(a,b); // nello stesso verso" } sort(Lastre,Lastre+N); // ordino le lastre per prima coordinata crescente cout << greedy() << endl; // calcolo il risultato e lo stampo return 0; }