#include #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 torre[MAX_N]; // vettore con l'elenco delle altezze delle massime torri (vedi sotto) int penultima[MAX_N]; // vettore con l'elenco della penultima lastra per le massime torri 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 massimatorre(int ultima) // funzione che calcola la massima altezza possibile per una torre con in cima { // l'ultima-esima lastra nell'ordine, ricorsivamente (con memorizzazione). if (torre[ultima] > 0) { // se ho gia' calcolato questo valore, lo restituisco senza ricalcolarlo. return torre[ultima]; // PROVATE A TOGLIERE questa riga: il programma diventa eterno } int massimaaltezza=1; // almeno so che posso fare una torre alta 1; poi for (int i=0; i Lastre[ultima].y) { // se funziona anche sulla y allora provo a sceglierla come penultima, if (massimatorre(i)+1 > massimaaltezza) { // se la torre viene piu' alta di quanto ho trovato finora, massimaaltezza = massimatorre(i)+1; // me lo segno. penultima[ultima] = i; // (mi segno anche quale blocco ho utilizzato per penultimo) } } } // cout << "massimatorre(" << ultima << ") = " << massimaaltezza << endl; // DEBUG return torre[ultima] = massimaaltezza; // restituisco la torre piu' alta che ho trovato, memorizzando il risultato. } 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" } Lastre[N].x = 0; //per comodita', aggiungo una lastra fittizia Lastre[N].y = 0; // che sta sopra a qualunque altra sort(Lastre,Lastre+N+1); // ordino le lastre per prima coordinata decrescente for (int i=0; i<=N; i++) { penultima[i] = -1; // cout << "Lastre[" << i << "] = (" << Lastre[i].x << " x " << Lastre[i].y << ")" << endl; // DEBUG } cout << massimatorre(N)-1 << endl; // calcolo la piu' alta torre che finisce con la ”lastra vuota", // meno 1 (perche' la lastra vuota in realta' non conta) for (int i=penultima[N]; i>=0; i=penultima[i]) { printf(" %5d x %-5d\n", Lastre[i].x, Lastre[i].y); } cout << "=======================" << endl; return 0; }