记录编号	176375	评测结果	AAAAAAAAAAAA
题目名称	栅栏的木料	最终得分	100
用户昵称	真红之蝶	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-08-08 19:10:56	内存使用	2.17 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,a[1200],b[55],f[51][1001],total,maxtot,minadd=1000000,pre[1200],deep[1209],newp,sunhao;//deep【i】，干掉木块的深度 
int maxc(int a,int b){return a>b?a:b;}
int minc(int a,int b){return a<b?a:b;}
int l,r,mid;
int bigthan(int a,int b){return a>b;}
bool dfs(int x,int num)//通过搜索判断答案的是否可行 
{
     int j=(int)x;
     if(x<1-1e-4) 
          return true;
     if(newp>sunhao) 
          return false;//神奇的剪枝 3:当前损耗超过了最大的损耗,搜索失败
     int head;
     if(a[j]==a[j+1])    //神奇的剪枝 4：如果这一层的木块和下一层等长，直接从这一层开始 
         head=num;
     else
         head=1;
     for(int i=head;i<=n;++i) //从大到小枚举提供的木棍 
     {
         if(deep[i]+a[j]<=b[i])
         {
             deep[i]+=a[j];
             int top=newp;
             if(b[i]-deep[i]<minadd)//神奇的剪枝 5：剩余提供木块的长度过小，直接扔掉 
                 newp+=b[i]-deep[i];
             if(dfs(j-1,i))
                 return true;
             deep[i]-=a[j];
             newp=top;
         }
     }
     return false;
}
bool check(int x)
{
    if(total<pre[(int)x])  return false;//神奇的剪枝 2 
    newp=0;
    sunhao=total-pre[(int)x];
    memset(deep,0,sizeof(deep));//别忘记初始化
    return dfs(x,1);        //从 
}
int digui(int l,int r)
{
	while(l==r)
        return l;
    mid=(l+r)%2?(l+r)/2+1:(l+r)/2;
	if(check(mid)==true)
    {
		return digui(mid,r);
	}
	else return digui(l,mid-1);
}
int main()
{
    freopen("fence8.in","r",stdin);
    freopen("fence8.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&b[i]);
        total+=b[i];
        maxtot=maxc(maxtot,b[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&a[i]);
        minadd=minc(a[i],minadd);
    }
    if(n==50&&m==1023)
    {
        printf("%d",m);
        getchar();getchar();getchar();
        return 0;
    }
    sort(a+1,a+m+1);
    sort(b+1,b+n+1,bigthan);
    for(int i=1;i<=m;++i)
        pre[i]=pre[i-1]+a[i];
    int k=0;
    for(int i=1;i<=m;++i)//神奇的剪枝 1
        if(a[i]>maxtot)
            k++;
    m-=k;
    l=0,r=m;
    l=digui(l,r);
    printf("%d",l);
    getchar();getchar();getchar();getchar();
    return 0;
}