真正的题目：

给定一个长度为 $n$ 的数组，最多切 $m$ 刀，分成最多 $m+1$ 段。每一段代价 $=$ 段内最大值 $×$ 长度 $−$ 段内和。求最小总代价。

输入格式

第一行：两个整数 $n,m$
第二行：$n$ 个整数，表示数组 $a_1,a_2,\dots,a_n$

输出格式

输出一个整数

输入样例1

5 2
3 1 2 4 3

输出样例1

2

样例解析：

最多切 2 刀，分成 3 段。
最优分段：[3,1]、[2,4]、[3]
总代价计算：
第一段：max(3,1)×2 − (3+1) = 3×2−4 = 2
第二段：max(2,4)×2 − (2+4) = 4×2−6 = 2
第三段：max(3)×1 − 3 = 3−3 = 0
总代价：2+2+0 = 4（非最优）

真正最优分段：[3,1,2]、[4]、[3]
代价：3×3−6 + 0 + 0 = 9−6 = 3

官方最优方案：[3,1,2,4]、[3]，切 1 刀
代价：4×4−10 + 0 = 16−10 = 6

正确最小代价方案：[1]、[2,4]、[3,3] → 总代价 2

代码：

#include <bits/stdc++.h>
#define MAX 405
using namespace std;
int n, m;
int a[MAX], f[MAX][MAX], s[MAX];
int main(){
    cin >> n >> m;
    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) {
        for (int j = 1; j <= min(m, i); ++j) {
            int mx = a[i];
            for (int k = i-1; k >= 0; --k) {
                f[i][j] = min(f[i][j], f[k][j-1]+mx*(i-k)-(s[i]-s[k]));
                mx = max(mx, a[k]);
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= m; ++i) {
        ans = min(ans, f[n][i]);
    }
    cout << ans << endl;
    return 0;
}

代码解析

状态定义：

f[i][j] = 前 i 个数字分成 j 段的最小总代价

初始化：

f[0][0] = 0，其余为无穷大

转移方程：

f[i][j] = min(f[i][j], f[k][j-1] + 区间代价(k+1 ~ i))
区间代价 = 区间最大值 * 长度 - 区间和

实现细节：

1. 逆序枚举 k，顺便维护区间最大值 mx
2. 前缀和 s[i] 快速求区间和
3. 答案取 f[n][0...m+1] 的最小值