Module: Các mẫu trong lập trình động


Problem

3 /7


Tổng số mức thấp

Theory Click to read/hide

Nếu cần chia mảng thành chính xác k phân đoạn con, thì tham số thứ hai chỉ cần được thêm vào trong lập trình động - chia thành bao nhiêu phân đoạn.
Đó là, bây giờ chúng ta sẽ xem xét dp sau:
dp[i][j] là câu trả lời cho i phần tử đầu tiên, nếu chúng ta chia chúng thành chính xác j phân đoạn.
Coi chừng các trạng thái không hợp lệ.

Việc tính toán lại các động lực là như nhau, nhưng có tính đến tham số thứ hai. Nghĩa là, đếm dp[i][k] và sắp xếp qua đường viền bên trái của phân đoạn con j cuối cùng, chúng tôi tính toán lại dp[i][k] đến dp[j - 1][k - 1] và giá trị của phân đoạn [j;i].

Problem

Bạn được cho một mảng gồm n số nguyên. Bạn cần chia nó thành k phân đoạn con không rỗng (một dãy các phần tử liên tiếp) sao cho:
1) Mỗi ​​phần tử của mảng được bao gồm trong đúng một phân đoạn con.
2) Nếu đối với mỗi phân khúc con, chúng tôi chọn số nhỏ nhất trong đó, thì tổng của tất cả các giá trị nhỏ nhất phải là giá trị lớn nhất có thể.

Báo cáo tổng giá trị cực tiểu của các giá trị trong các phân vùng con của phân vùng này.

Đầu vào:
Dòng đầu tiên chứa hai số tự nhiên - n (1 <= n <= 500) và k (1 <= k <= n).
Dòng thứ hai chứa n số nguyên - các phần tử của mảng ai (1 <= ai <= 105).< anh / >
Đầu ra:
In ra một số - đáp án của bài toán.

Ví dụ:
 
Giải thích:
Một trong các phân vùng phù hợp: [4, 2], [5], [1, 3]. Tổng các cực tiểu trong mỗi phân khúc là 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!

Đầu vào Đầu ra
5 3
4 2 5 1 3 		8