[es] - USACO zadatak ( number triangles )

TRIŠESTPET
Split , Hrvatska

Član broj: 24877
Poruke: 4
*.adsl.net.htnet.hr

ICQ: 162376918

Profil

^{13.07.2004. u 19:41 - pre 240 meseci}

Molim pomoc ( ideje ... ) u vezi ovog zadatka sa USACO-a . Sljedi copy/paste da ne bi bilo nekih pitanja ...

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

PROGRAM NAME: numtri
INPUT FORMAT
The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
SAMPLE INPUT (file numtri.in)
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

OUTPUT FORMAT
A single line containing the largest sum using the traversal specified.
SAMPLE OUTPUT (file numtri.out)
30

Odgovor na temu

Alef
Viktor Kerkez
Novi Sad

Član broj: 505
Poruke: 188
*.ftn.ns.ac.yu

Profil

Re: USACO zadatak ( number triangles )

^{13.07.2004. u 21:52 - pre 240 meseci}

Možeš da napraviš binarno stablo sa elementima (brojevima) koje si dobio, rekurzivno isprobaš sve moguće putanje i da zbirove slažeš u niz koji ima

elemenata (toliko ima putanja), gde je n broj vrsta. Onda nađeš najveći element niza.
Koliko vidim samo se najveći zbir i traži, ne i putanja.

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: USACO zadatak ( number triangles )

^{13.07.2004. u 22:32 - pre 240 meseci}

Rešenje može dosta da se ubrza ako se vidi da od tih svih puteva mnogi imaju zajedničke parcijalne puteve. Ovo je verovatno jedan od osnovnih problema u kojima može da se iskoristi tzv. dinamičko programiranje.

Posmatramo n-ti red trougla, i neki broj u njemu (recimo dvojka u poslednjem redu).

Pitamo se: koji je najveći mogući zbir među svim putevima koji se završavaju u tom broju. Pošto tih zbirova očigledno ima mnogo, na prvi pogled je nejasno kako možemo sve da ih pregledamo i pronađemo najveći. Međutim, postoji jednostavan trik koji rešava stvar.

Sve putanje koje se završavaju u broju 2 moraju da prođu kroz brojeve koji su gore-levo, odn. gore-desno u šemi (to su 4 odn. 7). Pretpostavimo sada da znamo koji su maksimalni zbirovi svih puteva koji se završavaju u 4, odn. u 7. Ako to znamo onda znamo i sledeće: maksimalni zbir svih puteva koji se završavaju u 2 jednak je većem od zbirova puteva za 4 i 7, uvećanom za 2.

Dakle AKO znamo maksimalne zbirove za 4 i 7, možemo da „proizvedemo“ maksimalni zbir za 2 jednostavnom operacijom (maksimum plus vrednost broja). Ostaje nam još da nekako sračunamo zbirove za 4 i za 7. To se može učiniti na isti način, gledanjem maksimalnih zbirova koji su gore-levo, odn. gore-desno, računanje maksimuma itd.

Još treba da se primeti da je sve maksimume u jednom redu moguće sračunati ako su poznati maksimumi iz prethodnog reda. Sada je rešenje jednostavno: pre nego što sračunamo maksimum u jednom redu, sračunaćemo sve maksimume u prethodnom, a zatim na osnovu njih i maksimume u tekućem.
Zahvaljujući tome što u ranijim redovima ima manje brojeva, problem je jednostavniji. Najprostije je sračunati maksimum u prvom redu u kome stoji samo jedan broj.

Dakle algoritam je:

– za prvi red, maksimum je jednak prvom i jedinom broju.
– maksimumi za trenutni red se izračunaju na osnovu poznatih maksimuma za prethodni red i gore pomenute formule, novosračunati maksimumi se zapamte za sledeći prolazak kroz petlju.
– pomerimo se na sledeći red i ponovimo prethodno.
– kad izvrtimo petlju za sve redove, prođemo kroz poslednji izračunati niz maksimuma i nađemo koji je najveći element.

f

Odgovor na temu