Prestatgeries òptimes P10475
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.
(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.
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
- Author
- Enric Rodríguez
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++