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 + ;

int n, k, dp[N], a[N];

bool check(int m)

{

    for (int i = n; i > ; i--)

    {

        dp[i] = n - i - ;

        for (int j = i + ; j <= n; j++)

        {

            if (abs(a[j] - a[i]) <= m * 1LL * (j - i))

                dp[i] = min(dp[i], dp[j] + j - i - );

        }

        if (dp[i] + i <= k)

            return true;

    }

    return false;

}

int main()

{

    cin >> n >> k;

    for (int i = ; i <= n; i++)

        cin >> a[i];

    int l = , r = 2e9;

    while (l < r)

    {

        int m = l + ((r - l) >> );

        //cout << l << " " << r << " "<<m<<"\n";

        if (check(m))

            r = m;

        else

            l = m + ;

    }

    cout << r;

    return ;

}

巴特西

有意思的DP（CF360B Levko and Array）

Codeforces 360B Levko and Array

最新文章

热门文章