Module: Corak dalam Pengaturcaraan Dinamik


Problem

3 /7


Jumlah rendah

Theory Click to read/hide

Jika perlu untuk membahagikan tatasusunan kepada betul-betul k subsegmen, maka parameter kedua hanya ditambah dalam pengaturcaraan dinamik - berapa banyak segmen untuk dibahagikan.
Iaitu, sekarang kita akan mempertimbangkan dp berikut:
dp[i][j] ialah jawapan untuk elemen i pertama, jika kita membahagikannya kepada segmen j yang tepat.
Berhati-hati dengan keadaan tidak sah.

Pengiraan semula dinamik adalah sama, tetapi mengambil kira parameter kedua. Iaitu, mengira dp[i][k] dan mengisih melalui sempadan kiri subsegmen terakhir j, kita mengira semula dp[i][k] melalui dp[j - 1][k - 1] dan nilai segmen [j;i].

Problem

Anda diberi tatasusunan n integer. Anda perlu membahagikannya kepada k subsegmen bukan kosong (jujukan elemen berturut-turut) supaya:
1) Setiap elemen tatasusunan telah disertakan dalam satu subsegmen.
2) Jika bagi setiap subsegmen kita memilih nombor minimum di dalamnya, maka jumlah semua minima hendaklah maksimum yang mungkin.

Laporkan jumlah minima nilai dalam subsegmen partition ini.

Input:
Baris pertama mengandungi dua nombor asli - n (1 <= n <= 500) dan k (1 <= k <= n).
Baris kedua mengandungi n integer - unsur tatasusunan ai (1 <= ai <= 105).< br / >
Output:
Cetak satu nombor - jawapan kepada masalah.

Contoh:
 
Penjelasan:
Salah satu partition yang sesuai: [4, 2], [5], [1, 3]. Jumlah minima dalam setiap sub-segmen ialah 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!

Input Output
5 3
4 2 5 1 3 		8