Courses

Dinamik program

Dinamik Programlamada Kalıplar

Module: Dinamik Programlamada Kalıplar

Problem

3 /7

düşüklerin toplamı

Theory Click to read/hide

Diziyi tam olarak k alt parçaya bölmek gerekirse, dinamik programlamada ikinci parametre basitçe eklenir - kaç parçaya bölünecek.
Yani, şimdi aşağıdaki dp'yi ele alacağız:
dp[i][j], onları tam olarak j parçaya ayırırsak, ilk i öğelerinin yanıtıdır.
Geçersiz durumlara dikkat edin.

Dinamiklerin yeniden hesaplanması aynıdır, ancak ikinci parametre dikkate alınır. Yani, dp[i][k]'yi sayarak ve son j alt bölümünün sol kenarlığını sıralayarak, dp[i][k]'yi dp[j - 1][k - 1]'e ve parçanın değerini yeniden hesaplarız [j;i].

Problem

Size bir n tamsayı dizisi verildi. Onu boş olmayan k alt parçaya (ardışık öğeler dizisi) bölmeniz gerekir, böylece:
1) Dizinin her elemanı tam olarak bir alt segmente dahil edildi.
2) Her bir alt bölüm için içindeki minimum sayıyı seçersek, tüm minimumların toplamı mümkün olan maksimum olmalıdır.

Bu bölümün alt bölümlerindeki değerlerin minimumlarının toplamını bildirin.

Giriş:
İlk satır iki doğal sayı içerir - n (1 <= n <= 500) ve k (1 <= k <= n).
İkinci satır n tamsayı içerir - a_i dizisinin öğeleri (1 <= a_i <= 10⁵).< br / >
Çıktı:
Bir sayı yazdır - sorunun cevabı.

Örnek:

Açıklama:
Uygun bölümlerden biri: [4, 2], [5], [1, 3]. Her bir alt segmentteki minimumların toplamı 2 + 5 + 1 = 8'dir.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking