题意

$\;$
现在有一个长度为$n$的序列$a$，你最多可以进行$k$次单点修改，最小化$max(|a_i-a_{i-1}|)$
$$n,k\leq 2\times 10^3,\; -10^9 \leq a_i\leq 10^9$$

样例

$\;$
$In:$
$6\;\;3$
$1 \;\;2 \;\;3 \;\;7 \;\;8 \;\;9$
$\;$
$out:$
$1$
$\;$

Solution

$\;$
看到最小化一个最大值这条信息，马上想到的应该就是二分。
所以我们二分答案这个最大值，问题就被我们转化成了：判断是否可以通过不超过 $k$ 次操作使得序列任意相邻两个数差的绝对值小于$mid$
而这个东西我们是可以DP的。但如何设计状态？
我们发现如果仅仅这样设计：”设$f_i$表示$1$到$i$中要满足条件最少要修改多少次”，这个东西是很难进行转移的，因为序列是会进行修改的，而这个DP状态无法考虑修改的情况。
我举个例子可能会更好理解一些：
正常地，按照这个例子，若$a_i$进行了修改，状态转移是：$f_i=min(f_i, f_{i-1} +1)$，条件是：$|a_i-a_{i-1}|>mid$
但我们发现：$f_{i-1}$这个值不一定是在$a_{i-1}$没被修改的情况下得到的。而若其恰好会被修改，换句话说，$a_{i-1}$并不是原来的值，那么$|a_i-a_{i-1}|>mid$这个条件就出现错误了
$\;$

正确设计状态

$\;$
所以我们针对$a_{i-1}$并不是原来的值这个问题来思考如何改进状态。
因为在原先的状态中，我们并不知道$a_{i-1}$是否被修改，所以我们不妨强制其不被修改，然后把DP值中” 最少要修改多少次 “改为” 最多有多少个数不被修改 “
那么状态就变为了：设$f_i$表示$1$到$i$中要满足条件最多有多少个数不被修改，且强制$a_i$不被修改。
而这里状态转移略微有些变化：由于我们不知道上一个不修改的地方是哪里，所以我们枚举$j\;(1\leq j < i)$
那么$[j+1,i-1]$这段区间进行修改需要满足的条件是$|a_i-a_j| \leq mid \times (i - j)$ (应该比较好理解)
直接$n^2$枚举进行状态转移，与$LIS$问题的转移方程有点类似
而最后判断是否可行时，我们需要枚举序列中最后一个没被修改的位置$x$，看看$f_x$是否$\geq n-k$。而如果整个序列找不到这样的$x$说明不可行
那么这道题就做完了。
时间复杂度：$O(n^2)$
$\;$

Code

#include <bits/stdc++.h>
const int N = 2010;
#define LL long long
int n, K, dp[N];
LL a[N];
LL get_abs(LL a, LL b)
{
      if(a < b) std::swap(a, b);
      return a - b;
}
bool check(LL mid)
{
      for(int i=1;i<=n;i++) dp[i] = 1;
      for(int i=1;i<=n;i++)
      for(int j=1;j<i;j++)
      {
      if(get_abs(a[i], a[j]) <= 1LL * (i - j) * mid) dp[i] = std::max(dp[i], dp[j] + 1);
      }
      for(int i=1;i<=n;i++) if(dp[i] >= (long long)n - K) return true;
      return false;
}
int main()
{
      scanf("%d%d", &n, &K);
      for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
      LL l = 0, r = 2000000000;
      while(l < r)
      {
      LL mid = (l + r) >> 1;
      if(check(mid)) r = mid;
      else l = mid + 1;
      }
      printf("%lld", l);
      return 0;
}