Maksymalny zysk ze sprzedaży sznurka

Zadanie 8 z 10 · rozdział 24Trudność: 3 z 3dprod cuttingoptymalizacja

Treść zadania

Masz sznurek o długości n i cennik: $c_d$ to cena kawałka o długości d (dla d = 1, 2, …, n). Ceny nie muszą rosnąć razem z długością. Możesz pociąć sznurek na dowolną liczbę kawałków o całkowitych długościach (albo nie ciąć go wcale) i sprzedać wszystkie kawałki. Oblicz maksymalny możliwy zysk.

Dane wejściowe

  • 1. linia: n — długość sznurka
  • 2. linia: n nieujemnych liczb całkowitych $c_1, c_2, \ldots, c_n$ oddzielonych spacjami

Dane wyjściowe

Jedna liczba całkowita — maksymalny zysk.

Ograniczenia

  • 1 ≤ n ≤ 500
  • $0 \le c_d \le 10^4$

Uwagi

  • Sprawdzanie wszystkich sposobów pocięcia (jest ich $2^{n-1}$) jest zdecydowanie za wolne — w testach n sięga kilkuset. Użyj programowania dynamicznego: najlepszy zysk dla długości d to maksimum z $c_k + \text{najlepszy}(d - k)$ po wszystkich długościach pierwszego kawałka k. Daje to czas $O(n^2)$.

Przykłady

Wejście
4
1 5 8 9
Wyjście
10

Najlepiej pociąć sznurek na dwa kawałki o długości 2: $5 + 5 = 10$.

Wejście
8
1 5 8 9 10 17 17 20
Wyjście
22

Kawałki o długościach 2 i 6: $5 + 17 = 22$.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 24

Trudniejsze zadania na listach: przekształcenia w miejscu, sumy prefiksowe, kopiec i programowanie dynamiczne. Liczy się nie tylko poprawny wynik, ale też dobry algorytm — w testach są także długie listy, na których rozwiązanie „sprawdzające wszystkie możliwości” nie zdąży się wykonać.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Lista liczb jest podawana w dwóch liniach: w pierwszej jest liczba elementów n, w drugiej n liczb całkowitych oddzielonych spacjami (o ile zadanie nie mówi inaczej).
  • Listę wynikową wypisuj w jednej linii, a jej elementy oddzielaj pojedynczą spacją (o ile zadanie nie mówi inaczej).
  • Indeksy liczymy od 0.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
7
Oczekiwane wyjście
7

Test 2

Nie uruchomiono
Wejście
3
1 1 10
Oczekiwane wyjście
10

Test 3

Nie uruchomiono
Wejście
4
3 5 8 9
Oczekiwane wyjście
12

Test 4

Nie uruchomiono
Wejście
4
2 5 7 8
Oczekiwane wyjście
10

Test 5

Nie uruchomiono
Wejście
5
0 0 0 0 0
Oczekiwane wyjście
0

Test 6

Nie uruchomiono
Wejście
10
1 5 8 9 10 17 17 20 24 30
Oczekiwane wyjście
30

Test 7

Nie uruchomiono
Wejście
7
0 3 0 0 0 0 0
Oczekiwane wyjście
9

Test 8

Nie uruchomiono
Wejście
150
2 6 9 12 14 19 21 24 26 28 32 37 40 38 43 45 49 48 53 65 66 70 62 74 80 78 82 76 88 89 84 98 103 107 110 100 106 112 123 119 114 134 116 120 133 127 147 139 150 162 147 141 158 171 168 162 155 157 167 171 171 173 170 178 205 196 204 193 188 222 195 197 204 214 238 213 221 227 237 224 254 255 247 261 268 274 256 247 245 248 280 258 252 297 271 276 295 308 276 306 270 318 301 282 337 315 346 349 304 316 303 305 339 325 352 363 372 332 355 334 336 357 329 346 389 401 412 366 403 390 385 385 391 420 409 405 398 428 424 452 422 404 407 391 399 413 436 404 474 443
Oczekiwane wyjście
487
Uruchom z własnymi danymi