http://codeforces.com/problemset/problem/837/D
Može li neko da mi objasni kako da rešim ovaj zadatak? Shvatio sam da ‘roundness - okruglost’ broja zavisi od broja dvojki i petica u samom broju, ali ne znam šta dalje da radim sa tim.
Da li si upoznat sa Dinamičkim programiranjem? Ako nisi, onda ti predlažem da prođeš linkovanu lekciju, i rešiš prvo neke lakše probleme koji se nalaze i u lekciji.
Ako si već radio neke slične probleme, onda je hint da stanje može da ti bude recimo
D[i][k][br2][br5] = da li možeš od prvih i brojeva da uzmeš tačno k, tako da do sada imas ukupno br2 dvojki i br5 petica
Rekurentna formula ti samo zavisi od toga da li uzimaš i-ti element ili ne. Ovo je rešenje u O(n^4), što bi trebalo da radi za data ograničenja, ali se relativno lako može i optimizovati da bude O(n^3) jer možemo izbaciti jednu od dimenzija (br2 ili br5) kao što je opisano u njihovom rešenju.
Slobodno piši ako ti ništa od ovog nije bilo jasno
Hvala na pomoći. Prvo ću morati da provežbam DP, pa ću se tada vratiti na ovaj zadatak, jer sam malo toga razumeo.