蒟蒻的题解

#include <bits/stdc++.h>

#define int long long

const long long maxn = 3e2 + 10;

using namespace std;

int n, m;

int a[maxn], dp[maxn][maxn], cnt[maxn];  //dp数组dp[i][j]表示 选择i个数时，最后的数字为a[j]时的最小花费

signed main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {

        cin >> a[i];

    }

    for (int i = 0; i <= m; i++) {

        for (int j = 0; j <= n; j++) {

            dp[i][j] = INT_MAX;//初始化

        }

    }

    for (int i = 1; i <= n; i++) dp[1][i] = 0;//无论怎样，选择一个数的花费为0

    for (int i = 2; i <= m; i++) {      //枚举选择数字的个数

        for (int j = 1; j <= n; j++) {  //枚举最后一个数

            for (int k = i - 1; k < j; k++) {//枚举倒数第二个数

                dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(a[k] - a[j]));

            }

        }


    }
    //考虑到之前枚举的第n个数可以不选，需要重新枚举，寻找最大值
    int ans = INT_MAX;

    for (int i = 1; i <= n; i++) {

        ans = min(ans, dp[m][i]);

    }

    cout << ans;

    return 0;
}