我们发现直接做dp是不行的 有后效性
又发现T是满足单调性的
想到二分 考虑check
先来想想如何确定一个区间内的数经过修改能否满足limit
我们肯定是要把这个区间内的数两两的差改的尽量递增地平均才行
写出式子就是
(a[j]-a[i])/(j-1)<=limit
设dp[i]表示 当前点是i(i不修改) 之后的满足要求的需要修改最小次数
然后对于当前i 枚举之后的不改的位置 就可以状态转移了 没有后效性
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define N 2005 using namespace std; template<class T> inline void read(T &x) { x=0; int f=1; static char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') f=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=f; } int n,k,a[N],dp[N]; //到了i 之后的满足要求的最小次数 inline bool check(int m) { for(int i=n;i>=1;i--) { dp[i]=n-i; for(int j=i+1;j<=n;j++) //枚举不改的位置 if(abs(a[j]-a[i])<=m*(j-i)) dp[i]=min(dp[i],dp[j]+(j-i-1)); if(dp[i]+i-1<=k) return true; } return false; } int main() { read(n); read(k); for(int i=1;i<=n;i++) read(a[i]); int l=0,r=2e9; while(l<r) { int m=(l+r)>>1; if(check(m)) r=m; else l=m+1; } cout<<l; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9844326.html
