题解：CF360B Levko and Array

endswitch · 2024-10-16 20:07:33 · 题解

技巧要点：

• 二分答案
• 转换性质（正难则反）

对于这一类形如最大值最小或最小值最大的问题通常都有一个二分答案的套路。

对于至多做 k 次修改这个限制可以转换为至少保留 n - k 个数。

那么我们的状态就呼之欲出了：dp_i 表示 [1, i] 中保留 i 的最多保留数。那么转移限制为 |a_i - a_j| \le x \times (j - i)，可以感性理解为 i 到 j 中若全都为最大值的最劣情况。

代码：

#include <bits/stdc++.h>
#define int long long
#define abs(x) ((x) < 0 ? -(x) : (x))
using namespace std;

const int N = 2e3 + 5;
int n, k, a[N], dp[N];

inline bool check(int x) {
    for(int i = 1 ; i <= n ; ++ i) {
        dp[i] = 1;
        for(int j = 1 ; j < i ; ++ j)
            if(abs(a[i] - a[j]) <= x * (i - j)) dp[i] = max(dp[i], dp[j] + 1);

        if(dp[i] + k >= n) return true;
    }

    return false;
}

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;

    for(int i = 1 ; i <= n ; ++ i)
        cin >> a[i];

    int l = 0, r = 2e9, ans = 0;

    while(l <= r) {
        int mid = (l + r) >> 1;

        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans;

    return 0;
}