题目大意

给定长度 $N$ 的整数序列 $A\{a_1, a_2, \ldots, a_N\}$，定义它的幅度 $R(A)$ 为：

$R(A) = \max \limits_{1 \le i \lt n}|a_{i+1} - a_i|$

现在，你可以选择至多 $K$ 个元素，并将他们改为任意整数。不同的元素，可以修改为不同的数值。

请计算，当你完成修改之后，序列的幅度最小是多少。

对于 $100\%$ 的数据，保证 $1 ≤ K ≤ N ≤ 2000$，$|a_i| ≤ 10^9$。

思路

首先，我们发现如果幅度变得越小则修改也越复杂和困难，那么我们可以在这样的情况下考虑能不能二分最大幅度。

那么我们二分后也就是要去尝试能不能构造出一个新序列 $B$ 让 $R(B)<=\text{二分的幅度}$ 同时修改操作 $\leq k$。

在之后这样的构造序列问题我们可以考虑 LIS，本质上就是从上一个满足一些条件的数转移到现在来同时接上。

那么本题的状态只有两个，改成某个值与不改。

但是如果我们考虑去 dp 前者会发现改成具体的某个值是需要枚举的，然后 $|a_i|\leq 10^9$ 明显炸掉。那么考虑枚举后者。

也就是 $dp[i]$ 表示以 $a_i$ 这个数不选的子序列的最小操作数。 那么，我们从之前的数里去枚举，之后发现对于 $i,j$，这两个数之间的拼接后中间的最大幅度可以算。是 $\lceil \frac{|a_i-a_j|}{i-j}\rceil$，为什么是 $i-j$ 呢，因为虽然改的数只有 $i-j-1$ 个，但是幅度有 $i-j$ 个。我们这个公式算的是幅度，所以要关心幅度。然后幅度要向上取整是因为这就是最小值了往下一点点都不行有要求改到最小整数所以只能改到向上取整了。 之后考虑 LIS 即可。

代码

#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;
const ll MAXN = 2005;
ll n, k, dp[MAXN], a[MAXN];

bool check(ll x) {
    for (int i = 1; i <= n; ++i) {
        dp[i] = i - 1;
        for (int j = 1; j < i; ++j) {
            if (ceil(abs(a[i] - a[j]) * 1.0 / (i - j)) <= x) {
                dp[i] = min(dp[i], dp[j] + (i - j - 1));
            }
        }
        if (dp[i] + n - i <= k) {
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    ll l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        r = max(r, abs(a[i] - a[i + 1]));
    }
    ll ans = 0;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

总结

再之后的二分可以考虑是不是一个数有没有单调性，感性就是一个数增大/减少要求就更困难/容易。

还有以后的序列类问题同时不要求构造的第一个就要想到 LIS，然后考虑怎么去转移。用选择那道题的思路。