[Terorista]

Imam problem sa prokorachenjem vremena.

Da bi najjeftinije unishtio sve spratove od a do b ja moram:
Ako najjeftinije unishtavanje spratova (a+1..b) potapa i a, onda je to reshenje
Ako ne, onda je reshenje jeftinije od ova dva:
- najjeftinije unishtavanje (a+1..b) + cena unishtavanja a-tog sprata
- min unishtavanje (a+1..b1) gde je b1 najnizhi sprat da je suma svih kolichina voda od a+1 do b1 vetja od vode potrebne za preplavljivanje a-tog sprata.

To je n * (n-1) / 2 brza koraka, izuzev trazhenja b1 shto je linearno.. Medjutim, limit vremena je 4 sekunde, shto je dosta. Ili neko ima neku drugu ideju za ovaj zadatak - samo me navedite na nju..

Pa kolko znam ogranicenje za n je 100.000 tako da ti algoritam u O(n^2) bas i nije od pomoci...

mozda gresim :)

O Bocicu, pa sto ne reche da si to ti (mozda bi ranije dobio odgovor:) :)

Prvo sto treba da primetish je da kada srushish neki sprat, do kraja ti je tacno odredjeno koje cesh sve spratove rushiti. E sad, kada srushish sprat N, izrachunas (i zapamtish) koje si josh spratove morao da rushish, i kolika je kolicina vode u njima. Kada budesh probao da srushish sprat N+1, necesh ici redom i gledati kako se svi ispod njega rushe, vec samo oni koje si u prethodnom koraku zapamtio ... E sad, da bi ti i to proslo na vremenu, moras da spratove koje pamtish smeshtas u heap, i da ih vadish prvo onog sa najmanje vode, i tako dalje ...

E, nadam se da si bar malo shvatio sta sam pokushavao da kazem (i ako deluje jako zbunjujuce:) ...

E mozda je njemu jasno, ali meni sigurno nije :)

Jel mozes jos jednom da objasnis kako treba da se radi, ali molim te pre toga se diskonetkuj, pa otkucaj, pa onda postuj, da ne bi brzgao i da ne bi opet bilo kako si i sam rekao zbunjujuce :)
Recimo kazes pamtimo kolicinu vode, mislis pocetnu kolicinu vode, ili kolicinu koja padne na taj sprat zbog ostalih itd.

Dakle, aj molim te ako nije problem, jedno lepo objasnjenje :)

pozzy