cf360 B. Levko and Array(二分答案,dp判断)(Cf360 B. levko and array)

题意:

修改数组中的不超过k个数,最小化相邻数之差的绝对值的最大值。

k <= n <= 2000

思路:

\(f(i)\) 表示第 \(i\) 个数不变,前 \(i\) 个数合法,至少要改变几个数。

初始化 \(f(i)=i-1\) 表示前面的数都改变。枚举 \(i\) 之前的所有 \(j\),把 \([j+1,i-1]\) 都改变,改成单调增或者单调减,那么 \(|a_i-a_j|/(i-j)\le ans\) 时ans合法。

对于每个 \(f(i)\),当 \(f(i)+n-i\le k\) 时有答案。即后面的数都改变。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2010;
int n, k, a[N], f[N];

bool pd(ll x)
{
    for(int i = 1; i <= n; i++) {
        f[i] = i - 1;
        for(int j = 1; j < i; j++)
            if(abs(a[i]-a[j]) <= x * (i-j))
                f[i] = min(f[i], f[j] + i-j-1);
        if(f[i] + n-i <= k) return 1;
    }
    return 0;
}

signed main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    ll l = 0, r = 2e9;
    while(l < r) {
        ll mid = l + r >> 1; //注意开ll
        if(pd(mid)) r = mid; else l = mid + 1;
    }

    printf("%lld", l);

    return 0;
}

————————

< strong > meaning of the question: < / strong >

Modify no more than k numbers in the array to minimize the maximum value of the absolute value of the difference between adjacent numbers.

k <= n <= two thousand

< strong > ideas: < / strong >

\(f (I) \) means that the number of \ (I \) remains unchanged, the number of the first \ (I \) is legal, and at least several numbers must be changed.

Initialization \ (f (I) = i-1 \) indicates that the previous numbers have changed. Enumerate all \ (J \) before \ (I \), change \ ([J + 1, I-1] \) to monotonic increase or monotonic decrease, then \ (|a_i-a_j| / (I-J) \ Le ans \) is valid.

For each \ (f (I) \), there is an answer when \ (f (I) + n-i \ Le K \). That is, the following numbers change.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2010;
int n, k, a[N], f[N];

bool pd(ll x)
{
    for(int i = 1; i <= n; i++) {
        f[i] = i - 1;
        for(int j = 1; j < i; j++)
            if(abs(a[i]-a[j]) <= x * (i-j))
                f[i] = min(f[i], f[j] + i-j-1);
        if(f[i] + n-i <= k) return 1;
    }
    return 0;
}

signed main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    ll l = 0, r = 2e9;
    while(l < r) {
        ll mid = l + r >> 1; //注意开ll
        if(pd(mid)) r = mid; else l = mid + 1;
    }

    printf("%lld", l);

    return 0;
}