# cf360 B. Levko and Array（二分答案，dp判断）(Cf360 B. levko and array)-其他

## cf360 B. Levko and Array（二分答案，dp判断）(Cf360 B. levko and array)

k <= n <= 2000

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

``````#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;
}

``````