题解（有用关注一个）

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

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

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

// 快速读入
inline int read() {
    int x = 0, f = 1; 
    char c = getchar();
    while (c < '0' || c > '9') { 
        if (c == '-') f = -1; 
        c = getchar(); 
    }
    while (c >= '0' && c <= '9') { 
        x = (x << 3) + (x << 1) + (c & 15); 
        c = getchar(); 
    }
    return x * f;
}

int main() {
    n = read(), m = read();
    m++;
    
    for (register int i = 1; i <= n; ++i) {
        a[i] = read();
        s[i] = s[i - 1] + a[i];
    }

    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;

    for (register int j = 1; j <= m; ++j) {
        for (register int i = j; i <= n; ++i) {
            register int mx = a[i];
            register int best = INF;
            register int si = s[i];
            
            // 从 i-1 往下遍历到 j-1
            for (register int k = i - 1; k >= j - 1; --k) {
                register int val = f[k][j - 1] + mx * (i - k) - (si - s[k]);
                if (val < best) best = val;
                if (a[k] > mx) mx = a[k];
            }
            f[i][j] = best;
        }
    }

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

这么写的