Zadaci s natjecanja -> C,C++,Pascal

Zadatak mozemo rijesiti primjenom klasicnog dinamickog programiranja.

dakle imamo array dp[ MAX_ROW ][ MAX_COL ];

dp[i][j] - oznacava maximalan broj bombona do pozicije i, j.

za svaku poziciju izracunamo :

dp[i][j] = max( dp[i-1][j], dp[i][j-1] ) + A[i][j]; // A - broj bombona na i,j pos.

moramo paziti samo na granicne slucajeve za i == 1 || j == 1

rjesenje je dp[N][M];

HINT : Zadatak je moguce rijesiti vec pri ucitavanju.

Dinamicko programiranje, hmm. Iako je poprilicno jednostavna ideja, tesko je objsniti sto je to zapravo.

Dinamicko programiranje, bio bi sistem razbijanja velikog problema na manje te potom rjesavanjem manjih, rijesiti veliki.

Dinamicko programiranje je razmjena, prostor za vrijeme. Tj. sve manje probleme koje izracunas, spremis tako da ih nemoras ponovno izracunat.

Napr, fibbonacijevi brojevi, ukoliko bi ih rjesavali rekurzivno.

fibo( 5 ) -> racunam fib(4) fib(3)

fib( 4 ) -> fib(3) fib(2)

...

kao sto vidmo u drugome redu, drugi puta racunam fib(3). Pa ako ga prvi puta spremim onda ga drugi puta samo vratim.

Ako se problem rjesava rekurzivno, tada se koristi memoizacija(spremanje).

No vijek je bolji bottom_up ako je moguc.

Mogao bi pisati jos satima, ali najbolje da pogledas ove zadatke, pa javis sto ti nije jasno.

Sto se tice naseg primjera :

U nizu dp, mi imamo rjesenja za sve pozicije, ne samo [N][M].

Dake dp[i][j] = max( dp[i][j-1], dp[i-1][j] ) + A[i][j], mi uzimamo bolje rjesenje između 2 postojeca.

Gledamo, jeli bolje doci do (i,j-1) pa skrenuti desno ili je bolje doci do (i-1, j) pa skrenuti dolje.

Dakle u nizu dp imamo spremljena SVA rjesenja od pozicije (1, 1).

Ovdje su klasicni primjeri.

http://forum.zrs.hr/index.php/topic,289.0.html

Razred, skola, grad ?

Prouci zadatak BOND, HONI 1.kolo 2006/2007. Veoma cesto bude, takav nekakav sablonski zadatak. I prosle i ove godine je bio(II podskupina).

http://www.spoj.pl/problems/KNAPSACK/

Evo problem na kojem je razrađena ideja dinamickog p.

Nemozes primjenjivat greedy rješenje, ovaj primjer se mora rjesavati DP-om.

http://www.dir.hr/pripreme/1998_1999/dinamicko.html

Ovdje je relativno dobro objasnjeno. S time da ovdje nije 1-0 knapsack.

Ne priority queue. Obicni Q na nacin da ubacis sve ulaze na pocetki.

for( int i = 0; i < R; ++i ) {

  scanf( "%s", mapa[i] );

  for( int j = 0; j < S; ++j ) {

    if( mapa[i][j] == 'U' ) {

      Q.push( make_pair(i, j) );

      p[i][j] = 0;

    }

  }

}

pa normalni bfs i dobit ces najkracu udaljenost izmedju svake tocke i

najblizeg ulaza. Mozda se moze sa PQ-om, ali ovo sigurno radi.

Ne , zasto ??

taj zadatak sam ja rjesio na taj nacin.

jednim bfs-om sam nasao udaljenos izmedju svake tocko i najblizeg stabla, pa binarnim pretrazivanjem nasao optimalan put.

Inace taj zadak se moze rjesiti PQ-om, ma da je slozenost skoro ista jer ubacivanje u Q kosta .

Nakon sto napravis matricu udaljenosto, napr dist[x][y].

napr

+..

..+

...

...

dist izgleda ovako

011

110

221

332

tada radis binarno pretrazivanje.

Ako mozes doci do jazbine s udaljenoscu 4 tada sigurno mozes i sa 3 , 2 ...

neka je doljnja granica 0, a gornja dist[ vukx ][ vuky ]

probas s mid = (donja + gornja) / 2

ako moze onda donja = min

else gornja = min - 1

to radi dok god je donja < gornja

kako probas, tako sto radis bfs od vuka do jazbine, a uvjet je da udaljenost mora biti veca ili jednaka onoj s kojom probas.

rjesenje je donja granica.

I kako je proslo zupanijsko... ako si bio

Ma otkad ovaj DUMP priprema zadatke kvaliteta se srozala skroz. A ja nisam bio na ocjenjivanju, inace sam rjesio sva 4. pa bumo vidli. Zadnji zadatak II podskupine ima pre nizak time limit pa necu ima 100% na tom zadatku. A ostalo bi trebalo biti dobro.

Ja nisam ni pročitao 4.,Na 3. sam se davio ko stoka....što je najgore taj 4. bih možda i mogao rješiti,kolko tolko znam MST

Zasto?