有意思的DP（CF360B Levko and Array）

刚才面试了一个蛮有意思的DP题目，脑子断片，没写出来，不过早上状态还是蛮好的

一个长度为n的序列最多改变k次，使相邻两数之差绝对值的最大值最小

三维的dp我先尝试写一下

Codeforces 360B Levko and Array

其实是n^2logm的，太nb了

去二分答案这个很好想，因为既然这个数满足，大于它肯定满足，然后就是去判断这个数字存不存在了。很容易想到贪心，但是贪心会有个问题，就是你无法确定你要修改的哪个数，很容易你就可以找到自己的bug。最后这个是个dp，dp[i]表示从n到i需要修改的最小的次数

当然是把全部往等差(这个差可以有符号)数列搞，我最初想的是找到平均数，平均数是不可能的，因为有时候改一个会很影响平均数

那就是判断这个数字合不合法，并不需要去判断这个数字需要改成什么，需要改成什么太难想的，因为其实满足的是一个范围

可以倒着来，因为这个满足了，之前的肯定满足。

然后就去找是不是有满足的，满足就是相当于在前一个状态上加上从i到j的差-1，和第一个一样

然后就可以判断了，非常完美的代码，佩服啊

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, k, dp[N], a[N];

bool check(int m)
{
    for (int i = n; i > 0; i--)
    {
        dp[i] = n - i - 1;
        for (int j = i + 1; j <= n; j++)
        {
            if (abs(a[j] - a[i]) <= m * 1LL * (j - i))
                dp[i] = min(dp[i], dp[j] + j - i - 1);
        }
        if (dp[i] + i <= k)
            return true;
    }
    return false;
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 0, r = 2e9;
    while (l < r)
    {
        int m = l + ((r - l) >> 1);
        //cout << l << " " << r << " "<<m<<"
";
        if (check(m))
            r = m;
        else
            l = m + 1;
    }
    cout << r;
    return 0;
}