Module: Pattern nella programmazione dinamica


Problem

3 /7


Somma dei minimi

Theory Click to read/hide

Se è necessario dividere l'array in esattamente k sottosegmenti, il secondo parametro viene semplicemente aggiunto nella programmazione dinamica: in quanti segmenti suddividere.
Cioè, ora considereremo il seguente dp:
dp[i][j] è la risposta per i primi i elementi, se li dividiamo esattamente in j segmenti.
Fai attenzione agli stati non validi.

Il ricalcolo della dinamica è lo stesso, ma tenendo conto del secondo parametro. Cioè, contando dp[i][k] e ordinando attraverso il bordo sinistro dell'ultimo sottosegmento j, ricalcoliamo da dp[i][k] a dp[j - 1][k - 1] e il valore del segmento [j;io].

Problem

Ti viene dato un array di n numeri interi. Devi dividerlo in k sottosegmenti non vuoti (una sequenza di elementi consecutivi) in modo che:
1) Ogni elemento dell'array è stato incluso esattamente in un sottosegmento.
2) Se per ogni sottosegmento scegliamo il numero minimo in esso, allora la somma di tutti i minimi dovrebbe essere il massimo possibile.

Riporta la somma dei minimi dei valori nei sottosegmenti di questa partizione.

Inserimento:
La prima riga contiene due numeri naturali: n (1 <= n <= 500) e k (1 <= k <= n).
La seconda riga contiene n numeri interi - gli elementi dell'array ai (1 <= ai <= 105).< br / >
Uscita:
Stampa un numero: la risposta al problema.

Esempio:
 
Input Uscita
5 3
4 2 5 1 3 		8

Spiegazione:
Una delle partizioni adatte: [4, 2], [5], [1, 3]. La somma dei minimi in ogni sottosegmento è 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!