codeforces-360B-Levko and Array-二分+dp

cf题目链接
北方高校第4次训练题目链接

题意:有n个数排成一列，现在你可以改变k个数的大小。问你max(|ai-ai+1|)的最小值是多少（a∈[0,2e10]）（两个题目都保证n^2log复杂度可以过）

orz，这题先是在wannafly的每日中见过……当时没做……然后这次西工大负责的北方高校训练又出了这道题……看来我们也可以出原题了

思路:很容易想到二分答案，关键是怎么进行可行性判断……假设二分的答案为x，dp[i]表示第i个数不变，前i个数的最大差值不超过x。转移dp[i]=min(dp[i],dp[j]+i-j-1)(j<i)，j要保证abs(a[i]-a[j])<=k*x（也就是i,j不变，改变中间的数）。这样，只要存在一个i使得dp[i]+n-i<=k就能判断x可行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
long long a[2002];
long long dp[2002];
long long INF=0x3f3f3f3f;
int n,k;
int judge(long long x)
{
	for(int i=1;i<=n;i++)dp[i]=i-1;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<i;j++)
	  if(abs(a[j]-a[i])<=(i-j)*x)
	  {
	  	dp[i]=min(dp[j]+i-j-1,dp[i]);
	  }
	int flag=0;
	for(int i=1;i<=n;i++)
	 if(dp[i]+n-i<=k)flag=1;
	return flag;   
}
int main()
{
	int T;
	//scanf("%d",&T);
	T=1;
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)scanf("%lld",a+i);
		long long l,r;
		l=0;r=2e9+1;
		long long ans;
		while(l<r-1)
		{
			long long mid=(l+r)/2;
			if(judge(mid)==1)r=mid;
			 else l=mid+1;
		}
		if(judge(r-1))r=r-1;
		if(judge(l))r=l;
		printf("%lld\n",r);
	}
	return 0;
}