[bzoj1082]栅栏

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,a[105],b[1005];
 4 bool dfs(int k,int s){
 5     if (s<0)return 0;
 6     if (!k)return 1;
 7     for(int i=1;i<=n;i++)
 8         if (a[i]>=b[k]){
 9             a[i]-=b[k];
10             if (dfs(k-1,s-a[i]*(a[i]<b[1]))){
11                 a[i]+=b[k];
12                 return 1;
13             }
14             a[i]+=b[k];
15         }
16     return 0;
17 }
18 int main(){
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
21     scanf("%d",&m);
22     for(int i=1;i<=m;i++)scanf("%d",&b[i]);
23     sort(a+1,a+n+1);
24     sort(b+1,b+m+1);
25     int l=0,r=m;
26     while (l<r){
27         int mid=(l+r+1>>1),s=0;
28         for(int i=1;i<=n;i++)s+=a[i];
29         for(int i=1;a[i]<b[1];i++)s-=a[i];
30         for(int i=1;i<=mid;i++)s-=b[i];
31         if (dfs(mid,s))l=mid;
32         else r=mid-1;
33     }
34     printf("%d",l);
35 }