题目大题：CF上的题目还是比较容易读懂的。这道题的意思嘛，他是说，有一个不超过2000个数的数组，每一个数与后面的数的绝对值称为value，那么所有当中最大的value就是整个数组的value，现在你有k次变换，每一次可以将其中的一个数变为任何一个使得数组价值最小的数。 假如题目的价值是所有的之和，也可以用这道题的方法。 思路： dp[i]表示的是到i这个位置，使得数组符合条件的最少变换次数。 这个符合条件就奇妙了，这个符合条件是由你定的，最终的符合条件就是答案。 简单来说：你举例一个答案，放进去，看看能不能使得整个数组的变换次数小于等于给定的K次，假如可以的话，那么这个数存起来。 接下来我们尝试更大一点可以不可以呢？可以的话重复以上操作，不可以的话就是之前的数拉。 我们枚举的范围是0-2e9，这么大的范围，傻眼了，不急，二分搜索是一个不错的方法。 好了，，方法说完了。接下来是考验你DP功底的时候了，可惜这边我差劲的很，没办法给大家切入点和突破性的建议和见解了。 只能给大家讲一下这个模型，放心，等我学成之后我定给大家剖析每一道我A的题。 dp[i]=min(dp[i],dp[j]+i-j-1)（1
;int dp[2010];int a[2010];const int inf = 2e9;int n, m;bool bs(long long mid){for (int i = 1; i <= n; i++){dp[i] = i – 1;for (int j = 1; j < i; j++)if (abs(a[i] – a[j]) <= (i – j)*mid)dp[i] = min(dp[i], dp[j] + (i – j – 1));if (dp[i] + n – i <= m)return true;}return false;}int main(){while (cin >> n >> m){for (int i = 1; i <= n; i++)scanf(“%d”, &a[i]);long long l = 0, r = inf;int ans = 0;while (l <=r){(bs(mid)){ans = mid; r = mid – 1;}else l = mid + 1;}cout << ans << endl;}}
不要做刺猬能不与人结仇就不与人结仇，
