神光

【題目描述】

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

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

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

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

【輸入格式】

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

【輸出格式】

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

【樣例輸入】

3 1 1
22
17

【樣例輸出】

4

【樣例解釋】

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

【資料規模】

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

對於$100\%$的資料，$1<=N<=2000，1<=R,G,Ai<=1,000,000,000$。

---

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

然後二分模板打好了，怎麼寫$check$函數呢……不會寫。

所以貼一波官方題解。

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

---

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

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

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

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

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

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

時間複雜度：$O(N^2)$

期望得分：$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;
}