题解

容易TLE 我们先来看下本题翻译——

贝茜喜欢观光，今天她正在寻找风景优美的山谷。
我们关注一个 N×N 的网格，每个格子都有一个高度。
网格外部的所有格子都可以视为具有无限高的高度。
山谷是网格中的一个区域，该区域是连通的、没有空洞，并且紧邻该区域的每一个格子的高度都高于该区域内所有格子的高度。 更正式的定义如下： 如果一个集合中的任意两个格子都可以通过一系列上、下、左、右移动互相到达，则称该集合为“边连通”的。
如果一个集合中的任意两个格子都可以通过一系列上、下、左、右或对角线移动互相到达，则称该集合为“点连通”的。 “区域”是指一个非空的边连通格子集合。 如果一个区域的补集（包括 N×N 网格外的无限格子）不是点连通的，则称该区域是“有洞的”。 一个区域的“边界”是指与该区域中某个格子正交相邻（上、下、左、右）但不属于该区域本身的格子集合。
“山谷”是指任何一个非有洞的区域，且该区域内每个格子的高度都严格小于其边界上每个格子的高度。
贝茜的目标是计算所有山谷的大小之和。 输入格式 第一行包含整数 N，其中 1≤N≤750。 接下来 N 行，每行包含 N 个整数，表示网格中每个格子的高度。每个高度 h 满足 1≤h≤10⁶。
所有高度均为互不相同的整数。 在至少 19% 的测试用例中，进一步保证 N≤100。

OKOK 那么现在我们来上题解

#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() + 1;  // 题目输入的 m 是段数-1，直接在此处转换

    for (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 (int j = 1; j <= m; ++j) {
        for (int i = j; i <= n; ++i) {
            int mx = a[i];
            int best = INF;
            int si = s[i];

            // 从 i-1 向下枚举分割点 k
            for (int k = i - 1; k >= j - 1; --k) {
                int val = f[k][j - 1] + mx * (i - k) - (si - s[k]);
                best = min(best, val);
                mx = max(mx, a[k]);  // 维护区间 [k+1, i] 的最大值
            }
            f[i][j] = best;
        }
    }

    int ans = INF;
    for (int j = 0; j <= m; ++j) {
        ans = min(ans, f[n][j]);
    }

    printf("%d\n", ans);
    return 0;
}