题意：

修改数组中的不超过k个数，最小化相邻数之差的绝对值的最大值。

k <= n <= 2000

思路：

\(f(i)\) 表示第 \(i\) 个数不变，前 \(i\) 个数合法，至少要改变几个数。

初始化 \(f(i)=i-1\) 表示前面的数都改变。枚举 \(i\) 之前的所有 \(j\)，把 \([j+1,i-1]\) 都改变，改成单调增或者单调减，那么 \(|a_i-a_j|/(i-j)\le ans\) 时ans合法。

对于每个 \(f(i)\)，当 \(f(i)+n-i\le k\) 时有答案。即后面的数都改变。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2010;
int n, k, a[N], f[N];

bool pd(ll x)
{
    for(int i = 1; i <= n; i++) {
        f[i] = i - 1;
        for(int j = 1; j < i; j++)
            if(abs(a[i]-a[j]) <= x * (i-j))
                f[i] = min(f[i], f[j] + i-j-1);
        if(f[i] + n-i <= k) return 1;
    }
    return 0;
}

signed main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    ll l = 0, r = 2e9;
    while(l < r) {
        ll mid = l + r >> 1; //注意开ll
        if(pd(mid)) r = mid; else l = mid + 1;
    }

    printf("%lld", l);

    return 0;
}