USACO 4.1.2 栅栏的木料

这个讲的超好....一定要看...然后看我代码就好懂啦...

http://blog.****.net/ta201314/article/details/41287567

各种优化确实非常好....搜索的一道好题...

挂代码：

/*
    Problem : USACO 4.1.2 栅栏的木料
    Author : Robert Yuan

    优化解释：
    0. 二分+贪心判断可行解 (根据自己设计的贪心算法尽量的得到一个比较靠近正确值的 ans,再后面的搜索的下界就会大大提高)
    1. 如果使用的木料与上一块的木料大小相同，那么上一块若没有选前 i块木板，这一块也不要选(1.若是因为前面的太小而不选，那么对于这个也太小  2.若是因为前面的情况已经搜过，那我选择前面的就成了一个已经搜索过的情况)
    2. 如果当前需要枚举的木板与上一块木板的大小相同，只选其中最后的那块，理由同上。
    3. 如果剩下的木板大小比第一块还小，那么就是属于余料，将所有余料和已经切好的木料减去，剩下的木板长度如果比未切好的 x个木料总长还要小，那么这种状态也是不可行的
*/

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

inline int in(){
    int x=;char ch=getchar();
    while(ch>'' || ch<'') ch=getchar();
    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
    return x;
}

const int maxn=;
const int maxm=;
const int INF=0x7f7f7f7f;

int n,m,S,ans;
int tmp[maxn];
int a[maxn],b[maxm],s[maxm];

bool cmp(const int &a,const int &b){
    return a>b;
}

bool dfs(int x,int last){
    if(!x) return true;
    if(S<s[x]) return false;/*优化 3*/
    S-=b[x];
    for(int i= x!=ans && b[x]==b[x+] ? last:/*优化 1*/;i<=n;i++){
        while(i<n && a[i]==a[i+]) i++;/*优化 2*/
        if(a[i]>=b[x]){
            a[i]-=b[x];
            if(a[i]<b[]) S-=a[i];
            if(dfs(x-,i)){
                if(a[i]<b[]) S+=a[i];
                a[i]+=b[x];    S+=b[x];
                return true;
            }
            if(a[i]<b[]) S+=a[i];
            a[i]+=b[x];
        }
    }
    S+=b[x];
    return false;
}

bool check(int m){/*优化 0*/
    int Minn,Minx;
    memcpy(tmp,a,sizeof(a));
    for(int i=m;i;i--){
        Minn=INF,Minx=-;
        for(int j=;j<=n;j++)
            if(tmp[j]>=b[i] && Minn>tmp[j])
                Minn=tmp[j],Minx=j;
        if(Minx<) return false;
        tmp[Minx]-=b[i];
    }
    return true;
}

int main(){
    n=in();
    for(int i=;i<=n;i++) a[i]=in(),S+=a[i];
    m=in();
    for(int i=;i<=m;i++) b[i]=in();

    sort(a+,a+n+);
    sort(b+,b+m+);

    for(int i=;i<=m;i++)
        s[i]=s[i-]+b[i];

    int l=,r=m,mid;

    if(check(r)){
        printf("%d",m);return ;
    }

    while(l+<r){
        mid=(l+r)>>;
        if(check(mid)) l=mid;
        else r=mid;
    }
    ans=r;
    while(dfs(ans,) && ans<=m) ans++;
    printf("%d",ans-);

    return ;
}