Module: 동적 프로그래밍의 패턴

Problem

n 정수의 배열이 제공됩니다. 이를 위해 비어 있지 않은 k개의 하위 세그먼트(연속 요소 시퀀스)로 나누어야 합니다.
1) 배열의 각 요소는 정확히 하나의 하위 세그먼트에 포함되었습니다.
2) 각 하위 세그먼트에 대해 최소 수를 선택하면 모든 최소값의 합이 가능한 최대값이어야 합니다.

이 파티션의 하위 세그먼트에 있는 값의 최소값 합계를 보고합니다.

입력:
첫 번째 줄에는 n(1 <= n <= 500)과 k(1 <= k <= n)의 두 자연수가 포함됩니다.
두 번째 줄에는 n개의 정수가 포함되어 있습니다. 배열 a_i(1 <= a_i <= 10⁵)의 요소입니다.< br / >
출력:
하나의 숫자를 인쇄하십시오 - 문제에 대한 답.

예:
  <몸>
설명:
적합한 파티션 중 하나: [4, 2], [5], [1, 3]. 각 하위 세그먼트의 최소값 합계는 2 + 5 + 1 = 8입니다.

입력	출력
5 3 4 2 5 1 3	8