Tekintsük a következő egyszemélyes játékot: A játék kezdetén egy sorban leraknak N darab pozitív egész számot. A játékos legfeljebb L lépést tehet. Egy lépésben a még a táblán lévő számsorból H darab egymás melletti számot levehet, a levett számok a pontszámához adódnak. A levett számok helye üresen marad, és lépés során a szomszédos számok között nem lehet üres hely. A játékosnak az a célja, hogy a lehető legtöbb pontot szerezze.

Készíts programot, amely kiszámítja, hogy legjobb esetben hány pontot szerezhet a játékos!

A szamos.be szöveges állomány első sorában három egész szám van, a kezdeti számsorozat számainak N száma, a lépések maximális L száma és az egyszerre levehető számok H darabszáma (1<=N<=3000, 1<=L<=1000, 2<=H<=N). A második sor tartalmazza a kezdeti játékállást, azaz N pozitív egész számot egy-egy szóközzel elválasztva. Minden szám értéke legfeljebb 5000.

A szamos.ki szöveges állomány első sora egy egész számot tartalmazzon, a játékban elérhető lehető legtöbb pont értékét! A második sor egy olyan lépéssort tartalmazzon, amellyel a maximális pontszám elérhető! Egy lépést a lépésben levett számsor első elemének sorszáma írjon le!

Bemenet	Kimenet
8 2 3 1 6 8 7 6 2 1 8	32 2 6

A feladat forrása: NTOITV 2012 2. forduló, 11-12. évfolyam

Algoritmusok: dinamikus programozás

megoldás