題干：

Levko has an array that consists of integers:?a1,?a2,?... ,?an. But he doesn’t like this array at all.

Levko thinks that the beauty of the array?a?directly depends on value?c(a), which can be calculated by the formula:

The less value?c(a)?is, the more beautiful the array is.

It’s time to change the world and Levko is going to change his array for the better. To be exact, Levko wants to change the values of at most?k?array elements (it is allowed to replace the values by any integers). Of course, the changes should make the array as beautiful as possible.

Help Levko and calculate what minimum number?c(a)?he can reach.

Input

The first line contains two integers?n?and?k?(1?≤?k?≤?n?≤?2000). The second line contains space-separated integers?a1,?a2,?... ,?an?(?-?109?≤?ai?≤?109).

Output

A single number — the minimum value of?c(a)?Levko can get.

Examples

Input

5 2 4 7 4 7 4

Output

0

Input

3 1 -100 0 100

Output

100

Input

6 3 1 2 3 7 8 9

Output

1

Note

In the first sample Levko can change the second and fourth elements and get array:?4,?4,?4,?4,?4.

In the third sample he can get array:?1,?2,?3,?4,?5,?6.

題目大意：

給一個n個元素的數組:?a1,?a2,?... ,?an。允許修改K個元素，使得max(abs(a[i]-a[i+1]))最小。（n<=2000）

Input

第一行輸出兩個整數n?and?k?(1?≤?k?≤?n?≤?2000). 第二行輸入n個整數a1,?a2,?... ,?an?(?-?109?≤?ai?≤?109).

Output

輸出相鄰兩個元素之差的最小值

解題報告：

首先這個題肯定具有單調性，所以二分這個最小值，然后check是否可以在修改K個數以內來滿足要求。

check(x)代表最小值數x的時候是否可以在修改K個數以內滿足要求，也就是check中的相鄰數的差的絕對值必須要<=x才行。check的時候選擇dp。dp[i]代表在第i個數不變的情況下，前i個數滿足相鄰數<=x的最少改變的數。轉移就是枚舉前面每一個數當上一個不變的數，那中間的數都是變的，注意可以更新的條件，是中間的數都貪心的去這個最大值時，是否可行，你假設x是10，然后a[i-1]是1，a[i]是1e9，那怎么也轉移不了對不對，所以貪心的策略，最大差值情況是剛好取公差為x的等差數列。然后取個最小值，并且默認在此條件下是否可以滿足條件，也就是后面的數也全改變的情況下是否滿足條件，滿足直接return 1即可。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e3 + 5; int dp[MAX]; ll a[MAX]; int n,k; bool ok(ll x) {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)*x) dp[i] = min(dp[i],dp[j]+(i-j-1));}if(dp[i] + (n-i) <= k) return 1;}return 0; }int main() {cin>>n>>k;for(int i = 1; i<=n; i++) cin>>a[i];ll l = 0,r = 2e9,mid,ans;while(l<=r) {mid = (l+r)>>1;if(ok(mid)) r = mid-1,ans = mid;else l = mid+1;} printf("%lld\n",ans);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 361D】Levko and Array （二分，dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。