CF360B题解

简述题意

定一个数列 \(a\)，可以对其中的元素做至多 \(k\) 次修改，每次修改可以将数列中的一个数改成另一个。
求经过修改后，\(max_{i=1}^{n} |a_i-a_{i-1}|\)

思路

考虑二分答案，对于 check 函数，我们可以利用 dp 进行求解。
由于修改不太好想，我们可以把问题转换为让不被修改的数最多。容易发现，如果有 \(a_1,a_2,a_3\) 3个数都需要修改，当 \(a_2\) 有值可以使得这两个差都满足条件，我们就可以稍改一个，即条件为 \(|a_i-a_j|<(i-j)\times x\)

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int a[2005];
int dp[2005];
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]>=n-k) return true;
	}
	return false;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int l=-1,r=2e9;//不知道为什么，l设为0或其他数都过不了，只有设为-1才能过
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}