神光

【題目描述】

亮亮成功地念出了咒語，石門緩緩地自動移開，一道道絢麗的神光從城堡內激射而出，亮亮好奇而又興奮地走入了城堡中，迎面有一座極長的魔法陣，

魔法陣可以看作一條直線，它被均勻地分成了 1000000000 1 000 000 000 1000000000個位置，一個位置可以看成是一個格子，有些位置上筑有法壇，一共 N N N座，亮亮只有破了眼前的魔法陣，才能繼續前進，而欲破法陣，必須毀掉所有的法壇，

亮亮身前有兩根法杖：一根顏色血紅，能發紅色神光，光芒可以籠罩連續 L L L個位置，并摧毀這 L L L個位置上所有的法壇，最多使用 R R R次；另一根顏色碧綠，能發綠色神光，光芒可以籠罩連續 2 L 2L 2L個位置，并摧毀這 2 L 2L 2L個位置上所有的法壇，最多使用 G G G次，

法杖的神奇之處在于， L L L的值必須由亮亮事先設定好，并且一經設定，便無法更改，亮亮需要在規定的次數下摧毀所有法壇，并且使得 L L L最小，

【輸入格式】

第一行三個整數 N , R , G N, R, G N,R,G， 第 i ( 2 < = i < = n + 1 ) i (2<=i<=n+1) i(2<=i<=n+1) 行一個整數 A i Ai Ai，表示第 i i i座法壇的位置，

【輸出格式】

只有一個整數，表示 L L L的最小值，

【樣例輸入】

3 1 1
22
17

【樣例輸出】

4

【樣例解釋】

亮亮將 L L L設為 4 4 4，并用紅色神光籠罩 21 ? 24 21-24 21?24位置，用綠色神光籠罩 1 ? 8 1-8 1?8位置，

【資料規模】

對于 50 % 50\% 50%的資料， N < = 100 N <= 100 N<=100；

對于 100 % 100\% 100%的資料， 1 < = N < = 2000 ， 1 < = R , G , A i < = 1 , 000 , 000 , 000 1 <= N <= 2000，1 <= R, G, Ai <= 1,000,000,000 1<=N<=2000，1<=R,G,Ai<=1,000,000,000，

這就二分啊！！十分明顯的二分啊！！

然后二分模板打好了，怎么寫 c h e c k check check函式呢……不會寫，

所以貼一波官方題解，

（居然是動歸，狀態轉移方程根本想不到好吧，）

演算法：首先我們注意到，當 R R R和 G G G的大小超過了 N N N時， L L L的最小值就是 1 1 1，因此，我們只需要考慮 R R R和 G G G小于 N N N的情況，于是 R , G R,G R,G的規模就降到了 2000 2000 2000以內，

顯然要采用二分答案的方法，那么問題轉化為，判斷給定的 L L L能否摧毀所有法壇，我們采用動態規劃方法，

首先將法壇的位置按照從小到大進行排序，

令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示，在用了 i i i次紅光， j j j次綠光的情況下，最多從第一座法壇開始，一直摧毀到第幾座法壇，那么狀態轉移方程即為 d p [ i ] [ j ] = max ? ( P [ d p [ i ? 1 ] [ j ] + 1 ] , Q [ d p [ i ] [ j ? 1 ] + 1 ] ) dp[i][j]=\max ( P[dp[i-1][j] + 1], Q[dp[i][j-1] + 1] ) dp[i][j]=max(P[dp[i?1][j]+1],Q[dp[i][j?1]+1])，

其中 P [ k ] P[k] P[k]表示使用一次紅光， 能從第 k k k座法壇向右（正向為右）連續摧毀到第幾座， Q [ k ] Q[k] Q[k]表示使用一次綠光，能從第 k k k座法壇向右連續摧毀到第幾座，

P P P和 Q Q Q陣列可以通過預處理得到，最終，我們只要判斷 d p [ R ] [ G ] dp[R][G] dp[R][G]的值是否為 N N N即可，

時間復雜度： O ( N 2 ) O(N^2) O(N2)

期望得分： 100 100 100

代碼如下：

#include<bits/stdc++.h>
#define N 2000+10
using namespace std;

int n,R,G;
int a[N];
int id1[N],id2[N];
int f[N][N];

bool check(int L){
	memset(id1,0,sizeof id1);
	memset(id2,0,sizeof id2);
	memset(f,0,sizeof f);
	
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++){
			if(a[j]-a[i]<L)id1[i]=j;
			if(a[j]-a[i]<L*2)id2[i]=j;
		}
		
	id1[n+1]=n,id2[n+1]=n;
	
	for(int i=0;i<=R;i++)
		for(int j=0;j<=G;j++){
			if(i>0)f[i][j]=max(f[i][j],id1[f[i-1][j]+1]);
			if(j>0)f[i][j]=max(f[i][j],id2[f[i][j-1]+1]);
		}
		
	if(f[R][G]==n)return true;
	else return false;
}

int main(){
	//freopen("light.in","r",stdin);
	//freopen("light.out","w",stdout);
	
	scanf("%d%d%d",&n,&R,&G);
	
	if(G+R>=n){
		printf("1");
		return 0;
	}
	
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		
	sort(a+1,a+n+1);
		
	int l=1,r=1e9;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	
	printf("%d",l);
	
	return 0;
}