Prestatgeries òptimes P10475

Statement

Es volen mostrar $n$ objectes en una paret. L’objecte $i$ es trobarà a la posició $(i, y_i)$ . Cada objecte tindrà exactament un prestatge horitzontal a sota seu (o just a la mateixa alçada) per aguantar-lo, de manera que els objectes aguantats per un mateix prestatge seran consecutius. Posar cada prestatge costa una constant $c$ , independentment de la mida del prestatge. A més, fixar a la paret un objecte que està $d$ unitats per sobre del seu prestatge costa $d$ . Podeu minimitzar el cost total?

Aquí podeu veure la solució òptima corresponent al primer exemple d’entrada. El cost és $3 \cdot 15 + (30 - 23) + (9 - 0) + (14 - 0) = 75$ .

(70,21)

(0,21) (0,15) (0,11.5) (0,7) (0,4.5) (0,0)

(2,21)(30,21) (2,15)(15,15) (2,11.5)(10,11.5) (2,7)(65,7) (2,4.5)(45,4.5) (2,0)(40,0)

(15,11.5)(15,15) (45,0)(45,4.5) (65,0)(65,7)

(10,11.5)(30,11.5)

(30,21)(40,21)

(40,0)(70,0)

(15,15)0.2 (25,11.5)0.2 (35,21)0.2 (45,4.5)0.2 (55,0)0.2 (65,7)0.2

Entrada

L’entrada consisteix en diversos casos, cadascun amb $c$ i $n$ , seguits de les $n$ alçades $y_i$ . Podeu suposar $1 \le c \le 10^9$ , $1 \le n \le 2000$ , i $0 \le y_i \le 10^9$ .

Sortida

Per a cada cas, escriviu el cost mínim possible.

Pista

La solució esperada és una programació dinàmica amb cost $\Theta(n)$ en espai i $\Theta(n^2)$ en temps.

Public test cases

Input

15 6  30 23 42 9 0 14
1 3  10 12 15
3 3  10 12 15
8 3  10 12 15
1000000000 8  0 1000000000 0 1000000000 0 1000000000 0 1000000000

Output

Information

Author: Enric Rodríguez
Language: Catalan
Official solutions: C++
User solutions: C++