神光

【题目描述】

亮亮成功地念出了咒语，石门缓缓地自动移开，一道道绚丽的神光从城堡内激射而出。亮亮好奇而又兴奋地走入了城堡中，迎面有一座极长的魔法阵。

魔法阵可以看作一条直线，它被均匀地分成了$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; }