YbtOj练习：二分3 攻击法坛

http://noip.ybtoj.com.cn/contest/15/problem/3

二分+DP （一开始贪心搞错了）

先把读入的坐标排序一遍。

设 L1[i]是在第i个法坛使用第一根法杖能覆盖到的最远的法坛的序号（因为法坛的坐标数字太大了，数组放不下），L2[i]同理。f[i][j]是在使用了i次第一根法杖，j次第二根法杖后哪能覆盖到的最远的法坛的序号。

这时候你可能就会问了：R和G那么大，这么DP不会超时嘛

因为当R+G>=n时，只要令L=1，就可以攻击到所有法坛，所以我们要DP的R和G都是不超过2000的（n的最大值）。

转移方程：f[i][j]=max(L1[f[i-1][j]+1],L2[f[i][j-1]+1])

代码：

#include<bits/stdc++.h>//
using namespace std;
const int N=2005;
int pos[N],n,t1,t2;
int l,r;
int f[N][N];
int L1[N],L2[N];
bool check(int x)
{
    memset(L1,0,sizeof(L1));
    memset(L2,0,sizeof(L2));
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
     for(int j=i;j<=n;j++)
     {
         if(pos[j]<=pos[i]+x-1) L1[i]=j;
         if(pos[j]<=pos[i]+2*x-1) L2[i]=j;
     }
    L1[n+1]=n;L2[n+1]=n;//这里一定要特殊处理，否则当我们处理到能够覆盖第n个法坛的方案时，更新后f[i][j]就会变成0 
    for(int i=0;i<=t1;i++)
     for(int j=0;j<=t2;j++)
     {
         if(i!=0) f[i][j]=L1[f[i-1][j]+1];
         if(j!=0) f[i][j]=max(f[i][j],L2[f[i][j-1]+1]);
     }
    return f[t1][t2]==n;
}
int main()
{
    scanf("%d%d%d",&n,&t1,&t2);
    if(t1+t2>=n) 
    {
        printf("1");
        return 0;
    }
    for(int i=1;i<=n;i++) scanf("%d",&pos[i]);
    sort(pos+1,pos+n+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;
}