Giới thiệu
include <iostream>
include <vector>
include <climits>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
// dp[i][j] - l?ng phí t?i thi?u khi đ? đi qua chư?ng ng?i v?t th? i v?i j l?n thay đ?i đ? cao
vector<vector<long long> > dp(n, vector<long long>(k + 1, LLONG_MAX));
// Kh?i t?o chi?u cao ban đ?u
for (int j = 0; j <= k; j++) {
dp[0][j] = 0; // Không có l?ng phí khi chưa thay đ?i g? ? chư?ng ng?i v?t đ?u tiên
}
// Duy?t qua các chư?ng ng?i v?t t? 1 đ?n n
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
for (int prev = 0; prev <= j; prev++) {
dp[i][j] = min(dp[i][j], dp[i-1][prev] + max(0, h[i] - h[i-1]));
}
}
}
long long result = LLONG_MAX;
for (int j = 0; j <= k; j++) {
result = min(result, dp[n-1][j]);
}
cout << result << endl;
return 0;
}