Bombers i iaies (2) P65894

Els bombers d’un país llunyà volen protegir les iaies que es troben en n escoles. Les escoles estan en fila en un carrer, numerades en ordre de la 1 a la n. A cada escola j hi ha i_j iaies. Els bombers poden formar g grups, i cada grup pot anar a una sola escola. Si un grup va a l’escola j, hi protegeix totes les iaies. A més, també protegeix indirectament la meitat de les iaies de l’escola j−1, suposant que existeixi i que no estigui ja protegida totalment per algun altre grup; i igualment amb l’escola j+1.

Quin és el màxim nombre de iaies que es poden protegir?

Entrada

L’entrada consisteix en diversos casos, cadascun amb g i n, seguides de les i_j. Suposeu 1 ≤ g ≤ n ≤ 3000, i que totes les i_j són naturals parells entre 2 i 10⁵.

Sortida

Per a cada cas, escriviu quantes iaies es poden protegir.

Pista

La solució esperada per a aquest problema consisteix en una programació dinàmica amb dues recurrències encreuades i cost O(g · n).