Module: Muster in der dynamischen Programmierung


Problem

3 /7


Theory Click to read/hide

Ist es erforderlich, die Masse auf genau k der Cut-offs zu teilen, so wird der zweite Parameter in der dynamischen Programmierung einfach hinzugefügt, wie viele Schnitte.
Ich meine, jetzt zählen wir den folgenden Punkt:
dp[i][j] - Antwort für die ersten i Elemente, wenn wir sie auf genau j der Schnitte brechen.
Halten Sie die Armen im Auge.

Die Änderung ist gleich, aber mit dem zweiten Parameter. Ausgehend von dp[i][k] und über die linke Linie des letzten Teilabschnitts j werden wir dp[i][k] durch dp[j-1][k-1] und den Schnitt [j;i] zählen.

Problem

Du hast eine Menge n-alle Zahlen. Sie müssen es in k von nicht-vasiven Schnitten (contracting Sequenz) so dass:
(1) Jedes Element der Masse ging genau einen Schnitt.
(2) Soll für jedes Teilstück die Mindestzahl gewählt werden, so ist die Summe aller Mindestwerte so weit wie möglich.

Melden Sie die Mindestwerte in den Unterabschnitten des Crashs.

Eingabe:
In der ersten Zeile sind zwei natürliche Zahlen angegeben: n (1 PO = n Ø = 500) und k (1 PO = k RP = n).
Die zweite Zeile gibt n ganze Zahlen - die Elemente der Masse aI (1 Zug = aI · 105.)

Ausgangsdaten:
Nehmen Sie eine Nummer, die Antwort.

Beispiel:
EingangsdatenAusgangsdaten
Artikel 3
4 2 5 1 3		8)

Beschreibung:
Ein geeigneter Crash: [4, 2], [5], [1, 3]. Der Mindestbetrag in jedem Unterabschnitt beträgt 2 + 5 + 1 = 8.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!