城市规划(planning)

考虑二分答案，显然想要更小的不美观度一定需要更多的修改次数，所以答案是符合二分性质的，二分之后考虑DP，设\(f[i]\)表示对于前\(i\)座大厦，在第\(i\)栋不修改的情况下满足不美观度条件最少所需修改次数，初始时\(f[i]=i-1\)，而这里要求第\(i\)栋不修改是为了方便转移,转移时若\(H_i,H_j\)之间的高度差不超过二分值的\(i-j\)倍，则可以在\(f[j]\)的基础上再修改\(i-j-1\)栋大厦的高度来达成不美观度条件，最后若存在某个\(f[i]+n-i\)不超过\(k\)则说明当前二分值可行
注意这里二分时\(l+r\)可能会超过int的范围，所以应该使用\((r-1)/2+l\)或者更大范围的类型来进行二分

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define MAXN 2005
#define LL long long
using namespace std;
inline int read()
{
    int num=0,sgn=1;
    char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if (ch=='-')sgn=-1,ch=getchar();
    while (ch>='0'&&ch<='9')num*=10,num+=ch-'0',ch=getchar();
    return num*sgn;
}
int n,k,h[MAXN];
int l,r,mid;
bool check(int m)
{
    int dp[MAXN];
    memset(dp,0,sizeof(dp));
    for (int i=1;i<=n;i++)
        dp[i]=i-1;
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            if ((LL)abs(h[i]-h[j])<=(LL)(j-i)*(LL)m)
                dp[j]=min(dp[j],dp[i]+j-i-1);
    for (int i=1;i<=n;i++)
        if (dp[i]+n-i<=k)return 1;
    return 0;
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    l=0;r=2000000000;
    while (l<=r)
    {
        mid=l+(r-l)/2;
        if (check(mid))r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}