题解：CF360B Levko and Array

· · 题解

Pro

求在至多修改 k 次的情况下，\max\limits^n_{i=2}|a_i-a_{i-1}| 的最小值。

Sol

1. 二分答案

这题的二分挺明显的：因为如果能使 ans 成立，ans+1 一定成立；ans 不成立，ans-1 一定不成立。

2. 怎么 check

考虑外面套一个二分答案，考虑中间怎么 check。

check 的问题是：修改至多 k 次，能否使 \max\limits^n_{i=2}|a_i-a_{i-1}| 的答案等于 mid。

3. DP 状态

1.0: 定义 dp_i 为前 i 个数满足条件最少需要的修改次数。

但是这么写会很难受，因为我们没有一个定值，这个值不动，不方便我们 DP。

2.0: 定义 dp_i 为前 i 个数满足条件最少需要的修改次数，其中 \mathbf i 不修改。

这样子我们可以通过 a_i 来推断前面的 DP 状态了。

4. DP 方程

考虑 dp_i 和 dp_j 的关系。

先考虑 dp_j 什么时候才能转到 dp_i。

这是一个植树问题。a_j\sim a_i 中，有 i-j+1 棵树，即 i-j 个空格，空格长度不能超过 ans，即当且仅当 a_i-a_j\le (i-j)\times ans 成立，dp_j 才能转移到 dp_i。

然而就这么简单一个四年级小盆友都会的植树问题，很多题解都没有写为什么，甚至还有写什么感性证明的。

方程：显然把 j+1 \sim i 的数字全部改了就可以了。即

dp_{i}=\min \{dp_j+i-j-1\}

有人说：这肯定不是最优的啊。比如这个 hack：

1 2 3 4 4 4 4 4
      j       i

中间的三个 4 根本没有必要去修改啊？

但是这只是在这个 j 的情况，如果 j 移动到 i 前面一个时，阁下又该如何应对？

5. DP 初值

把所有数都改成 a_i 就好了。即 dp_i=i-1。

6. 如何判断

显然，dp_i 这玩意没有考虑到 i+1\sim n 这 n-i 个数，全改了就行。

所以 dp_i 实际上修改的总次数为 n-i+dp_i。

7. 核心代码

memset(dp,127,sizeof(dp)); // 不对啊你是来干什么的
for(int i=1;i<=n;i++) dp[i]=i-1;
for(int i=1;i<=n;i++)
  for(int j=1;j<i;j++)
  {
    int len=i-j+1; // 小学植树问题
    if(abs(a[i]-a[j])<=(len-1)*ans)
      dp[i]=min(dp[i],dp[j]+len-2);
  }
for(int i=1;i<=n;i++)
  if(n-i+dp[i]<=k) return 1;
return 0;

8. 时空复杂度分析

空间复杂度：O(n)。

时间复杂度：里面一个 n^2，外面一个 \log A，总时间复杂度 O(n^2\log A)，其中 A 是 a_i 的值域。