h2. 'Curse de cai':problema/cai

Vom sorta caii lui Gigel si Ionel in ordine descrescatoare si ii vom renumerota conform acestei ordini. Vom considera ca Gigel decide pentru fiecare cal al lui Ionel, in ordinea sortata, ce cal de-al sau sa ii opuna in cursa. Solutia prezentata in continuare se bazeaza pe urmatoarea observatie. Sa presupunem ca Gigel a decis ce cai de-ai sai vor concursa impotriva primilor $i$ cai ai lui Ionel si urmeaza sa decida pentru al $i+1-lea$ cal. Singurele doua variante fezabile pe care le are Gigel este sa aleaga cel mai bun cal al sau (dintre cei ramasi) si sa il puna sa concureze cu al $i+1$-lea cal al lui Ionel sau sa aleaga cel mai prost cal al sau. Vom calcula o matrice $C[i][j]$ reprezentand costul maxim pe care il poate obtine Gigel daca i-au mai ramas caii de la $i$ la $j$ (asta inseamna ca toti caii de la $1$ la $i-1$ au fost deja selectati si la fel si toti caii de la $j+1$ la $N$; de aici rezulta ca Gigel a ales dja adevrsai pentru primii $N-j+i-1$ cai de-ai lui Ionel si acum trebuie sa aleaga adversar pentru urmatorul cal al lui Ionel). $C[i][j]$ se calculeaza pe baza lui $C[i+1][j]$ (daca Gigel alege cel mai bun cal al sau impotriva calului curent al lui Ionel) sau pe baza lui $C[i][j-1]$ (daca elege cel mai prost cal al sau), alegandu-se varianta de cost maxim.

Vom sorta caii lui Gigel si Ionel in ordine descrescatoare si ii vom renumerota conform acestei ordini. Vom considera ca Gigel decide pentru fiecare cal al lui Ionel, in ordinea sortata, ce cal de-al sau sa ii opuna in cursa. Solutia prezentata in continuare se bazeaza pe urmatoarea observatie. Sa presupunem ca Gigel a decis ce cai de-ai sai vor concursa impotriva primilor $i$ cai ai lui Ionel si urmeaza sa decida pentru al $i+1-lea$ cal. Singurele doua variante fezabile pe care le are Gigel este sa aleaga cel mai bun cal al sau (dintre cei ramasi) si sa il puna sa concureze cu al $i+1$-lea cal al lui Ionel sau sa aleaga cel mai prost cal al sau. Vom calcula o matrice $C[i][j]$ reprezentand costul maxim pe care il poate obtine Gigel daca i-au mai ramas caii de la $i$ la $j$ (asta inseamna ca toti caii de la $1$ la $i-1$ au fost deja selectati si la fel si toti caii de la $j+1$ la $N$; de aici rezulta ca Gigel a ales deja adversari pentru primii $N-j+i-1$ cai de-ai lui Ionel si acum trebuie sa aleaga adversar pentru urmatorul cal al lui Ionel). $C[i][j]$ se calculeaza pe baza lui $C[i+1][j]$ (daca Gigel alege cel mai bun cal al sau impotriva calului curent al lui Ionel) sau pe baza lui $C[i][j-1]$ (daca elege cel mai prost cal al sau), alegandu-se varianta de cost maxim.

h2. 'Cercuri':problema/cercuri