暴力出奇迹……
原题：
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购
买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需
要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长
度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰
最多能够得到多少他所需要的木板。
m<= 50，n <= 1000
第一眼就脑补出暴力做法二分+dfs，然而想了想觉得dfs的复杂度非常不大丈夫啊
然后搜题解，就是dfs……
首先需要的木条递增排序然后降序dfs，对于每次搜到的木条遍历所有大木条
两个剪枝
搞个前缀和s[i]表示从第1到第i个需要的木条的长度和，用tot表示提供的木条的总长度，如果某个大木条剩下的部分比需要的最小的木条还短，这个大木条就相当于浪费掉了，加到一个waste里面，如果某层dfs中dfs到的木条的前缀和+waste比tot大，就直接return
如果当前木条和下一层要dfs到的木条长度一样，下一层搜的时候就直接从当前木条使用的大木条往后遍历（如果不一样就只能从1开始遍历了
然后这样剪枝直接把复杂度50^1000的dfs_1s跑过了……
暴力出奇迹……
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
int n,m; int a[],b[];
int wst=,s[],tt=,p;
bool dfs(int x,int y){
if(!x) return true;
if(wst+s[p]>tt) return false;
bool flg;
for(int i=y;i<=n;++i)if(a[i]>=b[x]){
a[i]-=b[x];
if(a[i]<b[]) wst+=a[i];
flg=dfs(x-,(b[x]==b[x-] ? i : ));
if(a[i]<b[]) wst-=a[i];
a[i]+=b[x];
if(flg) return true;
}
return flg;
}
int bnrsch(int l,int r){
int md;
while(l+<r){ md=(l+r)>>; (dfs(p=md,) ? l : r)=md;}
return dfs(r,) ? r : l;
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n;
for(int i=;i<=n;++i) tt+=(a[i]=rd());
sort(a+,a+n+);
cin>>m;
int mn=,mx=m;
for(int i=;i<=m;++i) b[i]=rd();
sort(b+,b+m+);
for(int i=;i<=m;++i){
s[i]=s[i-]+b[i];
mn+=(a[i]>b[i]); if(s[i]>tt) mx=min(mx,i-);
}
cout<<bnrsch(mn,mx)<<endl;
return ;
}