解题思路

给定长度为 n 的数组，需要把它划分为 m 个连续区间，使所有区间的“价格波动值”(区间内最大值减最小值)之和最小。 这是一类典型的“划分型动态规划(Partition DP)”问题。

状态设计

• 设 dp[i][k] 表示把前 i 个元素划分成 k 个连续区间时的最小代价。

• 转移：最后一个区间如果是 (j+1 … i)，则

  $$dp[i][k] = \min_{k-1 \le j < i}\{\, dp[j][k-1] + cost(j+1,i) \,\} $$

  其中 cost(l, r) 是子数组 a[l..r] 的 (max - min)。

区间代价的计算

• 直接预处理所有 cost(l,r) 需要 O(n^2)，但 DP 仍需三重循环。
• 更简洁做法：在计算 dp[i][k] 时，从 j=i-1 向左扫描，维护当前区间 (j+1..i) 的 curMax、curMin，其差即为所需代价。这样不用额外数组，常数也小。

边界与答案

• dp[0][0]=0，其余初始化为正无穷。
• 只在 i ≥ k 时有意义。
• 答案为 dp[n][m]。 特殊情况自然包含其中：m=n 时每段单点，答案为 0；m=1 时答案为整个数组的 max-min。

该做法为 O(m·n^2)，在 n≤500 时完全可行。

复杂度分析

• 时间复杂度：外层枚举 k=1..m、i=k..n，内层对每个 (i,k) 逆向扫描 j 最多 i-k+1 次，总体为 O(m·n^2)。
• 空间复杂度：dp 表大小为 (n+1)×(m+1)，为 O(n·m)。若使用两层滚动数组可降到 O(n)，本文保留全表，代码更直观。

代码实现

Python

import sys

INF = 10**30

def solve(a, n, m):
    # dp[i][k]：前 i 个元素划分为 k 段的最小代价
    dp = [[INF] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for k in range(1, m + 1):
        for i in range(k, n + 1):
            cur_max = -10**18
            cur_min = 10**18
            # 最后一段是 (j+1 .. i)，j 从 i-1 往左到 k-1
            for j in range(i - 1, k - 2, -1):
                val = a[j]
                if val > cur_max:
                    cur_max = val
                if val < cur_min:
                    cur_min = val
                cost = cur_max - cur_min
                if dp[j][k - 1] + cost < dp[i][k]:
                    dp[i][k] = dp[j][k - 1] + cost
    return dp[n][m]

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0]); m = int(data[1])
    a = list(map(int, data[2:2+n]))
    print(solve(a, n, m))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    // 计算把前 i 个元素分成 k 段的最小代价
    static long solve(int[] a, int n, int m) {
        long INF = (long)9e18;
        long[][] dp = new long[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int k = 0; k <= m; k++) dp[i][k] = INF;
        }
        dp[0][0] = 0;

        for (int k = 1; k <= m; k++) {
            for (int i = k; i <= n; i++) {
                long curMax = Long.MIN_VALUE;
                long curMin = Long.MAX_VALUE;
                // 最后一段是 (j+1 .. i)
                for (int j = i - 1; j >= k - 1; j--) {
                    int v = a[j];
                    if (v > curMax) curMax = v;
                    if (v < curMin) curMin = v;
                    long cost = curMax - curMin;
                    long cand = dp[j][k - 1] + cost;
                    if (cand < dp[i][k]) dp[i][k] = cand;
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());

        System.out.println(solve(a, n, m));
    }
}

C++

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

// 计算把前 i 个元素分成 k 段的最小代价
long long solve(const vector<long long>& a, int n, int m) {
    const long long INF = (long long)9e18;
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, INF));
    dp[0][0] = 0;

    for (int k = 1; k <= m; ++k) {
        for (int i = k; i <= n; ++i) {
            long long curMax = LLONG_MIN, curMin = LLONG_MAX;
            // 最后一段是 (j+1 .. i)
            for (int j = i - 1; j >= k - 1; --j) {
                long long v = a[j];
                if (v > curMax) curMax = v;
                if (v < curMin) curMin = v;
                long long cost = curMax - curMin;
                dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost);
            }
        }
    }
    return dp[n][m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << solve(a, n, m) << "\n";
    return 0;
}

题目内容

某超市有一排 $n$ 个连续的货架，每个货架上摆放的商品有一个单价。超市计划将这排货架分成 $m$ 个连续的促销区域。

每组区域是连续的货架区间，例如可以是第 $2-5$ 个货架,但不能是第 $2-3$ 个和第 $5$ 个货架。

每个促销区域的“价格波动值”定义为该区域内商品单价的最大值减去最小值。特别地，如果单独一个货架成为促销区域，那么它的价格波动值为 $0$ 。

超市希望所有促销区域的价格波动值之和最小，以此吸引更多顾客。请你帮助他们计算将 $n$ 个货架分成 $m$ 个连续区域后，价格波动值之和的最小值。

输入描述

第一行包含两个整数 $n$ 和 $m$ ，分别表示货架的总数和要分成的区域数量.

第二行包含 $n$ 个整数 $a$ ,依次表示从左到右每个货架上商品的单价。 $1<=m<=n<=500,1<=a_i<=1,000,000,000$.

输出描述

一行，一个整数,表示所有区域的价格波动值之和的最小值.

样例1

输入

4 2
3 1 4 2

输出

3

说明

其中一种可行的方法为:将第一个货架分为一个促销区域，将后三个货架分为一个促销区域。促销区 $1$ 的价格波动值为 $0$ ，促销区 $2$ 的价格波动值为 $3$ ，波动值总和为 $3$ .

可以证明没有其他方案可以使波动值总和更小。