Milyen módszerrel oldjam meg? (c#)

Mi a cél? A lehető legmagasabb tornyot kell felépíteni?

Milyen algoritmusokat tanultatok?

-Mi az nagy, zöld és nem hallod, ha a hátad mögé lopakodik?

-????

-Hihetetlen Hulk.

Szerintem előszöris rendezd növekvő sorrendbe súly szerint.

Ekkor lesz egy ilyesmi számsorod, ami a magasságokat jelenti:

2 1 3 2 5 7 4 9 3 13 11 12 14 10

Ebből már csak egy "részsorozat" kell kiválasztani, aminek az összege maximális.

Vedd sorba a magasságokat és egy listában tarts karban, hogy az adott elemet felhasználva mekkora a maximális torony

Most egy közbenső lépést írok le példának:

A 6. lépést követően ez a listád (Az első szám csak az adott helyen lévő magasságot jelenti):

2-2, 1-1, 3-5, 2-4, 5-10, 7-17, 4-, 9-, 3-, 13-, 11-, 12-, 14-, 10-

A következő magasság 4

Megkeresed a listában azt a legnagyobb számot, amelyik olyan helyen áll, amire a 4-est rá (vagyis alá) tudod helyezni.

Ez a 3-5, mert a 2-2, 1-1, 3-5, 2-4 jöhetne szóba (baloldali szám <=4), ezek közül ennél a legnagyobb a jobboldali szám. Az aktuális helyen tehát a maximális magasság: 5+4=9, tehát ezután a lépés után a számsorod:

2-2, 1-1, 3-5, 2-4, 5-10, 7-17, 4-9, 9-, 3-, 13-, 11-, 12-, 14-, 10-

Az algoritmus végén: (ha nem rontottam el)

2-2, 1-1, 3-5, 2-4, 5-10, 7-17, 4-9, 9-26, 3-8, 13-39, 11-37, 12-49, 14-63, 10-36

Ebből a listából már csak a legnagyobb (jobboldali) számot kell kiválasztnai. Tehát 63 a legmagasabb torony.

Ha szökséged van a konkrét kockákra is, akkor egye újabb listában tarts karban, hogy egy adott kockát melyikre raksz rá.

Amúgy gratu a tanárodnak, ez nem egy olyan gagyi kérdés, amit itt gykn fel szoktak általában tenni. Azt sem mondom, hogy legoptimálisabb az algoritmus, de legalább polinom idejű. Ha jobban érdekel, akkor neten olyasmire keress rá, hogy longest increasing subsequence (persze ha tudsz angolul, és ez nem is teljesen az, ami neked kell, dehasonló probléma)