12ms 4.3M

#include <bits/stdc++.h>
using namespace std;

const int MAX = 405;
const int INF = 0x3f3f3f3f;

int n, m;
int a[MAX], f[MAX][MAX], s[MAX];

int main() {
if (scanf("%d %d", &n, &m) != 2) return 0;
for (int i = 1; i <= n; i) {
scanf("%d", &a[i]);
s[i] = s[i-1] + a[i];
}
m;

// 初始化
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;

for (int i = 1; i <= n; ++i) {
    int max_j = min(m, i);
    for (int j = 1; j <= max_j; ++j) {
        int mx = a[i];
        // 原代码中 min_k = max(0, j-1 - 1) 即 j-2，但保留原逻辑
        int min_k = max(0, j - 2);
        for (int k = i - 1; k >= min_k; --k) {
            int cand = f[k][j-1] + mx * (i - k) - (s[i] - s[k]);
            if (cand < f[i][j]) f[i][j] = cand;
            if (a[k] > mx) mx = a[k];
        }
    }
}

int ans = INF;
for (int j = 1; j <= m; ++j) {
    if (f[n][j] < ans) ans = f[n][j];
}
printf("%d\n", ans);
return 0;

}