题目
思路
看完题目之后就有着一种打爆搜的冲动，当然是我们喜欢的DFS啦。m<=50为什么不打DFS呢？
注意题目中要的答案并不是直接爆搜就可以快速的找到。我们还需要加一些“特技”！
没错，就是二分答案！！！ 再用爆搜判断这个答案是否可以要（就是二分中的check）。
当然还要剪枝，不然TLE会让你十分难受。
下面说一下这题要用到的剪枝方法：
- 将提供的木材和需要的木材排序
- 记录浪费的长度，先前我们已经排好序了，二分时答案就应该是可行的mid，它的意思就是满足前mid块小的需要木板。有一种理想情况是最浪费的一种。比这种情况还浪费的直接剪枝！
- ……(还有好的剪枝方法，但蒟蒻直说到这里，如果还会TLE，请大家在想想，排完序后可能还可以做一些事情
我也不知道，别找我) - 哦，还有等效的剪枝，大家看看代码领悟一下。
还有一些我没说的细节，比如为什么b数组要从大到小开始搜索？ last是干什么的？
最浪费的理想情况是什么？ 希望大家可以想一想。
代码
下面给出代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
int ans,n,m,a[2000],b[2000],tot,sum[2000],mid,w;
int read(){//快读不解释
int X=0;bool w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
bool dfs(int h,int last){
bool ff=false;
if(tot-w<sum[mid]) return 0;//剪枝2
if(h==0) return 1; //如果尝试的木板都成功解决，就返回true
for(int i=last;i<=m;i++)
if(a[i]-b[h]>=0){//如果可以要，那就试试
a[i]-=b[h];
if(a[i]<b[1]) w+=a[i];//记录浪费的值
if(b[h]==b[h-1]) ff=dfs(h-1,i);
else ff=dfs(h-1,1);
if(a[i]<b[1]) w-=a[i];//作为DFS，回溯是要的
a[i]+=b[h];
if(ff==true) return 1;//如果之后的尝试中返回可行，那就返回true
}
return 0;//如果尝试的一切都未能成功，只好返回false
}
int main(){
n=read();//输入不解释
for(int i=1;i<=n;i++)
a[i]=read(),tot+=a[i];//tot指的是提供的木板总长，用于剪枝。
m=read();
for(int i=1;i<=m;i++)
b[i]=read();
sort(a+1,a+n+1);
sort(b+1,b+m+1);//排序使DFS时可以更方便的剪枝
for(int i=1;i<=m;i++)
sum[i]=sum[i-1]+b[i];//这是需要的木板长度的前缀和，用于剪枝。
while(sum[m]>tot)m--;
int l=0,r=m;//二分，当答案为m时是最理想情况，故r=m。
while(l<=r){
w=0,mid=l+r>>1;
if(dfs(mid,1)==1)//DFS判断是否可行
ans=mid,l=mid+1;//可行的话保存答案并且l变大尝试更大
else r=mid-1;//r变小尝试更小的是否可行
}
cout<<ans<<endl;//输出不解释
return 0;
}
蒟蒻的小小分析到这里结束了，谢谢观看！