NOIP模拟赛 城市规划

题意

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

解法

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

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

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

接下来我们思考状态转移，设我们此时二分的答案为，我们发现如果对于，如果，那么就说明我们总可以通过调整和之间（不包括）的座建筑物达到我们需要二分的答案。因此状态转移方程为：

那么最后总体上为了达到二分的答案所需要的最小修改数是多少呢？是吗？其实并不是，因为对于，最坏情况下我们还需要修改后面的座建筑物，因此总的最小修改数为：

接下来就可以愉快的二分答案了，总的复杂度为，还有要注意的是如果你采用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;
}