目录
题目描述
对于一个数组 \(A\) 定义 \(F(A)=max{abs(a[i]−a[i+1])};\) 给定一个数组，最多修改其中 \(k\) 个元素，只能把数修改成整数，求 \(F(A)\) 的最小值。
题目分析
这题很容易想到是二分，二分 \(F(A)\)。
check 是用 dp 。
- 状态
mid:相邻两数的差不超过 \(mid\)。
i:表示搜到第 \(i\)。
j:表示 \(1~i-1\)的一个数。
dp[i]:表示 \(i\) 不改变的最小修改的元素个数。 - 初始化
很容易想到dp[i]=i-1。 - 转移
如果\(|a[i]-a[j]|\)小于相邻两数的差的最大值*差的数量，
那就改i~j中间的数使差值平均，
否则改了也不满足条件。
所以状态转移方程就是：
if(abs(a[i]-a[j])<=x*(i-j))
dp[i]=min(dp[i],dp[j]+i-j-1);
要修改的个数就是sum=min(dp[i]+n-i);(假设后面都要改)
题目代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,k,a[N],dp[N];
bool check(int x)
{
int sum=n+1;
for(int i=1;i<=n;i++)
{
dp[i]=i-1;
for(int j=1;j<i;j++)
if(abs(a[i]-a[j])<=x*(i-j))
dp[i]=min(dp[i],dp[j]+i-j-1);
sum=min(sum,dp[i]+n-i);
}
return sum<=k;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int l=0,r=1e9;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))r=mid-1;
else l=mid+1;
}
cout<<l;
return 0;
}