题意

有 \(n\) 座高度为正整数的建筑物，定义不美观度为相邻建筑物高度差绝对值的最大值，你可以任意改动至多 \(k\) 座建筑物的高度，求能够达到的最小不美观度。

\(k \le n \le 2000, h \le 2 \times 10^9\)

解法

从数据范围看出这应该是一道 DP 题，所以很容易陷入的一条歪路就是，定义 \(f[i, j]\) 为前 \(i\) 座建筑物修改了 \(j\) 次的最小不美观度，然后会发现没办法消除后效性当场去世。

但是如果我们把题目 paraphrase 一下，变成：在修改至多 \(k\) 座建筑物高度的情况下，最大的相邻高度差最小是多少？首先我们发现随着修改数增加，不美观度肯定是可以单调递减的，其次我们从这熟悉的句型就发现这其实是一道二分答案的题目，问题就变成了如何判定一个不美观度能不能达到了，我们还是需要使用 DP 来完成。

定义 \(f[i]\) 为修改前 \(i - 1\) 座建筑物但是不修改 \(i\) 的情况下为了达到我们二分的答案所需要的最小修改数，我们把它们全部初始化为 \(i - 1\)，即最坏情况下前面的我们都需要修改。

接下来我们思考状态转移，设我们此时二分的答案为 \(x\)，我们发现如果对于 \(j < i\)，如果 \(|h_j - h_i| \le (i - j)x\)，那么就说明我们总可以通过调整 \(i\) 和 \(j\) 之间（不包括 \(i, j\)）的 \(i - j - 1\) 座建筑物达到我们需要二分的答案。因此状态转移方程为： \[ f[i] = \min_{1 \le j < i, |h_j - h_i| \le (i - j)x} \{ f[j] + i - j - 1\} \] 那么最后总体上为了达到二分的答案所需要的最小修改数是多少呢？是 \(\min_{1 \le i \le n} \{f[i]\}\) 吗？其实并不是，因为对于 \(f[i]\)，最坏情况下我们还需要修改 \(i\) 后面的 \(n - i\) 座建筑物，因此总的最小修改数为： \[ \min_{1 \le i \le n} \{f[i] + n - i\} \] 接下来就可以愉快的二分答案了，总的复杂度为 \(O(n^2\log h_{max})\)，还有要注意的是如果你采用 int mid = (l + r) / 2 的话是会爆 int 的，解决方法是使用 int mid = l + (r - l) / 2：

#include <cstdio>

using namespace std;
const int INF = 0x7fffffff;
const int N = 2010;
int f[N], h[N];
int n, k;

#define abs(a) ((a) > 0 ? (a) : -(a))
#define min(a, b) ((a) < (b) ? (a) : (b))

int valid(int x) {
    for (int i = 1; i <= n; i++)
        f[i] = i - 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++)
            if (abs(h[i] - h[j]) <= 1ll * x * (i - j))
                f[i] = min(f[i], f[j] + i - j - 1);
    }
    int ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, f[i] + n - i);
    return ans;
} 

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    int l = 0, r = INF;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (valid(mid) <= k) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}