KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

S. 109.

(10 points)

Deadline expired on 10 October 2016.


Google Translation (Sorry, the solution is published in Hungarian only.)

Használjuk a dinamikus programozás módszerét. Az első fa minden \(\displaystyle i\) pontjára és a második fa minden \(\displaystyle j\) pontjára tároljuk az \(\displaystyle i\)-edik pont által meghatározott részfának a \(\displaystyle j\)-edik pont által meghatározott részfává alakítás minimális költségét (dp[i][j]).

Ha az üres részfát felvesszük egy speciális pontként, akkor összesen három eset van:

1) Üres részfát üres részfává ingyen átalakíthatjuk

Ha valamelyik részfa nem üres, akkor

2) a bal részfát a bal részfává, a jobb részfát a jobb részfává alakíthatjuk, vagy

3) a jobb részfát a bal részfává a bal részfát a jobb részfává alakíthatjuk

A második és a harmadik eset függ a fában a két pont gyerekeire kiszámított értékektől. (A pontos képletek a mintamegoldásban olvashatók)

A kiszámítás sorrendjére használhatjuk a mélységi bejárás szerinti elhagyási sorrendet (mivel így a gyerekekre előbb számítódik ki az érték, mint a szülőre), vagy még egyszerűbb, ha dinamikus programozás helyett rekurzívan oldjuk meg a feladatot memorizálással. A mintamegoldás az utóbbi módon működik.

A futási idő \(\displaystyle O(n\cdot m)\), a megoldás \(\displaystyle O(n\cdot m)\) memóriát használ.

main.cpp


Statistics on problem S. 109.
17 students sent a solution.
10 points:Alexy Marcell, Bálint Martin, Busa 423 Máté, Csenger Géza, Gáspár Attila, Gergely Patrik, Horváth 546 János, Janzer Orsolya Lili, Kovács 246 Benedek, Nagy Ábel, Németh 123 Balázs, Noszály Áron, Olexó Gergely, Szakali Benedek.
6 points:1 student.
3 points:1 student.
1 point:1 student.


  • Problems in Information Technology of KöMaL, September 2016

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley