koliko vas je preslo/prelazi usaco? kako idu pripreme za drzavno, odakle se spremate i sl.? ja nisam nesto previse ambiciozan... ove godine se prvi put takmicim, i prelazim po malo usaco, sad sam kod greedy algoritma (usput, ako ima neko ideju za zadatak barn repair neka mi posalje pm ako moze..)
usaco
Ja radim samo takmicenja na njemu..
Postavi text zadatka ovde..
Valjda ne mogu svi da vide text posto se ide nekim redom..
Postavi text zadatka ovde..
Valjda ne mogu svi da vide text posto se ide nekim redom..
Zadatak se radis dinamicki:
Pre svega, ukupan broj stala S, nas ne zanima toliko nego nas samo zanimaju stale u kojima se nalaze krave (npr u primeru datom na usacu, ti neces da stavljas vrata na 44, 45...). Sa d [i, k] oznacimo minimalnu duzinu da prvih i krava zatvorimo sa k pregrada. Dakle, kranje resenje ce biti d [C,M]. Na pocetku sortiras stale po rednim brojevima, i to pamtimo u nizu p[i]. d [i,j] racunas kao:
d [i][j] = min {d [j][k-1] + (p[i] - p [j + 1] + 1)}, j \in {k-1,..., i-1}
tj. za zadnju pregradu probas sve mogucnosti, a za preostale si vec izracunao.
(mozda sam pograsio u ovome +- 1, ali ovo ti je princip)
Pre svega, ukupan broj stala S, nas ne zanima toliko nego nas samo zanimaju stale u kojima se nalaze krave (npr u primeru datom na usacu, ti neces da stavljas vrata na 44, 45...). Sa d [i, k] oznacimo minimalnu duzinu da prvih i krava zatvorimo sa k pregrada. Dakle, kranje resenje ce biti d [C,M]. Na pocetku sortiras stale po rednim brojevima, i to pamtimo u nizu p[i]. d [i,j] racunas kao:
d [i][j] = min {d [j][k-1] + (p[i] - p [j + 1] + 1)}, j \in {k-1,..., i-1}
tj. za zadnju pregradu probas sve mogucnosti, a za preostale si vec izracunao.
(mozda sam pograsio u ovome +- 1, ali ovo ti je princip)
Objasnio sam mu ja greedy resenje na private..
Ne moras dinamicko da radis..Samo sortiras rastojanja izmedju
susednih stala i ukljucis prvih C-M (valjda)..
Ne moras dinamicko da radis..Samo sortiras rastojanja izmedju
susednih stala i ukljucis prvih C-M (valjda)..