Clasa a XI-a/Programare dinamică/Probleme diverse folosind programare dinamică (pagina 3)
Probleme diverse folosind programare dinamică · Probleme de informatică
Știai că! Pe InfoAs, problemele sunt atent selectate și verificate pentru a asigura o experiență de învățare optimă.
Prosop
Problemă dificilă din Cupa InfoAs, ediția 8
Avem o listă cu n clanuri. Fiecare clan are un anumit nivel de atractivitate. Algoritmul lui Prosop funcționează în felul următor: dându-se doi indici st și dr, merită să atacăm clanurile de pe pozițiile st, st + 1, ..., dr - 1, dr cu scorul asociat min a[st..dr] · max a[st..dr]. Ceilalți membri ai clanului lui Prosop au dubii în privința algoritmului său, așa că îl pun la încercare. Știind n și nivelurile de atractivitate a celor n clanuri, să se răspundă la q întrebări de forma (st, dr) cu semnificația: care este scorul asociat atacului clanurilor de pe pozițiile de la st la dr?
21 de probleme respectă filtrele.
Alege clasa Șterge