问题 A: [SCOI2005]栅栏
时间限制: 1 Sec 内存限制: 162 MB
题目描述
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购
买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需
要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长
度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰
最多能够得到多少他所需要的木板。
输入
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长
度。接下来一行(即第m+2行)为整数n(n <= 1000)，表示约翰需要多少木材。接下来n行表示他所需要的每一块木板
的长度。木材的规格小于32767。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。
输出
只有一行，为约翰最多能够得到的符合条件的木板的个数。
样例输入
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30
样例输出
7
提示
25切出 21 30切出 20 40切出 19、18 50切出 15、16、17
主要就是考虑各种剪枝。设n块的是A，m块的是B.
根据贪心策略，先满足较小的A板一定最优，先用较小的B板最优。
然后，来二分可能的答案。
再然后，如果浪费的板子长度加上当前答案要求的总长度>B板总长度，返回。
然后如果B[i]==B[i-1]，那么他满足一个什么对称性。。。我不懂，但这时，对B板的枚举可以改变范围，也就是从当前枚举的i开始。（具体看代码）
没了。。。→_→
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int m,n,c[55],a[55],b[1025],B[1025],sum,mid,w;
inline int dfs(int x,int pos)
{
if(!x)return 1;
if(B[mid]+w>sum)return 0;
for(int i=pos;i<=m;i++)
if(c[i]>=b[x])
{
c[i]-=b[x];
if(c[i]<b[1])w+=c[i];
if(b[x]==b[x-1]){if(dfs(x-1,i))return 1;}
else if(dfs(x-1,1))return 1;
if(c[i]<b[1])w-=c[i];
c[i]+=b[x];
}
return 0;
}
int yjn()
{
cin>>m;for(int i=1;i<=m;i++)scanf("%d",&a[i]),sum+=a[i];
cin>>n;for(int i=1;i<=n;i++)scanf("%d",&b[i]);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)B[i]=b[i]+B[i-1];
sort(a+1,a+m+1);
while(b[n]>a[m])n--;
int l=0,r=n,ans;
while(l<=r)
{
mid=(l+r)/2;w=0;memcpy(c,a,sizeof(a));
if(dfs(mid,1))ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
}
int qty=yjn();
int main(){;}