Module: Padrões em Programação Dinâmica


Problem

3 /7


Soma dos mínimos

Theory Click to read/hide

Se for necessário dividir a matriz em exatamente k subsegmentos, o segundo parâmetro é simplesmente adicionado na programação dinâmica - em quantos segmentos dividir.
Ou seja, agora vamos considerar o seguinte dp:
dp[i][j] é a resposta para os primeiros i elementos, se os dividirmos em exatamente j segmentos.
Cuidado com estados inválidos.

O recálculo da dinâmica é o mesmo, mas levando em consideração o segundo parâmetro. Ou seja, contando dp[i][k] e classificando pela borda esquerda do último subsegmento j, recalculamos dp[i][k] até dp[j - 1][k - 1] e o valor do segmento [j;i].

Problem

Você recebe uma matriz de n inteiros. Você precisa dividi-lo em k subsegmentos não vazios (uma sequência de elementos consecutivos) para que:
1) Cada elemento do array foi incluído em exatamente um subsegmento.
2) Se para cada subsegmento escolhermos o número mínimo nele, então a soma de todos os mínimos deve ser o máximo possível.

Informe a soma dos mínimos dos valores nos subsegmentos desta partição.

Entrada:
A primeira linha contém dois números naturais - n (1 <= n <= 500) e k (1 <= k <= n).
A segunda linha contém n inteiros - os elementos da matriz ai (1 <= ai <= 105).< br / >
Saída:
Imprima um número - a resposta para o problema.

Exemplo:
 
Entrada Saída
5 3
4 2 5 1 3 		8

Explicação:
Uma das partições adequadas: [4, 2], [5], [1, 3]. A soma dos mínimos em cada subsegmento é 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!