Programozás‎ > ‎Feladatok‎ > ‎

Számjáték (NT)

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 K lépést tehet. Egy lépésben a még a táblán lévő számsorból két egymás melletti számot levehet, a levett számok a pontszámához adódnak. A levett számok helye üresen marad, és a 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. 

Feladat

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

Bemenet

A jatek.be szöveges állomány első sorában két egész szám van, a kezdeti számsorozat számainak N száma, és a lépések maximális K száma (1<=N<=10000, 1<=K<=1000). 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. 

Kimenet

A jatek.ki szöveges állomány egyetlen sora egy egész számot tartalmazzon, a játékban elérhető lehető legtöbb pont értékét!

Példa

Bemenet  Kimenet
6 2
1 6 8 7 6 2
27


Tesztadatok

Címkék

A feladat forrása: NTOITV 2012. 2. forduló, 9-10. évfolyam
Algoritmusok: dinamikus programozás

megoldás