Prestatgeries òptimes P10475


Statement
 

pdf   zip

thehtml

Es volen mostrar n objectes en una paret. L’objecte i es trobarà a la posició (i, yi). 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 · 15 + (30 − 23) + (9 − 0) + (14 − 0) = 75.

 ‍ ‍ ‍ ‍ ‍ (70,21) unit=0.17cm, linewidth=2

(0,21)42 (0,15)30 (0,11.5)23 (0,7)14 (0,4.5)9 (0,0)0

[linewidth=1pt,linestyle=dotted](2,21)(30,21) [linewidth=1pt,linestyle=dotted](2,15)(15,15) [linewidth=1pt,linestyle=dotted](2,11.5)(10,11.5) [linewidth=1pt,linestyle=dotted](2,7)(65,7) [linewidth=1pt,linestyle=dotted](2,4.5)(45,4.5) [linewidth=1pt,linestyle=dotted](2,0)(40,0)

linecolor=green -(15,11.5)(15,15) -(45,0)(45,4.5) -(65,0)(65,7)

linecolor=orange -(10,11.5)(30,11.5)

linecolor=red -(30,21)(40,21)

linecolor=brown -(40,0)(70,0)

linecolor=black

[fillcolor=black,fillstyle=solid](15,15)0.2 [fillcolor=black,fillstyle=solid](25,11.5)0.2 [fillcolor=black,fillstyle=solid](35,21)0.2 [fillcolor=black,fillstyle=solid](45,4.5)0.2 [fillcolor=black,fillstyle=solid](55,0)0.2 [fillcolor=black,fillstyle=solid](65,7)0.2

Entrada

L’entrada consisteix en diversos casos, cadascun amb c i n, seguits de les n alçades yi. Podeu suposar 1 ≤ c ≤ 109, 1 ≤ n ≤ 2000, i 0 ≤ yi ≤ 109.

Sortida

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

Pista

La solució esperada és una programació dinàmica amb cost Θ(n) en espai i Θ(n2) 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

    75
    3
    8
    15
    5000000000
    
  • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++