[文章目录]
Description
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。m<= 50，n <= 1000
二分+dfs???
贪心选的话显然是选前ans小的规格，二分ans，之后dfs判定？计算当前一定浪费的木板长度剪枝，还有木材枚举顺序也是从大到小。神之搜索QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s[1010],len[60],a[1010],tmp,sum,was;
bool dfs(int step)
{
if(!step) return true;
if(was+tmp>sum) return false;
int i,tmp;
for(i=m;i>=1;--i) if(len[i]>=a[step])
{
len[i]-=a[step];
if(a[1]>len[i]) was+=len[i];
tmp=dfs(step-1);
if(a[1]>len[i]) was-=len[i];
len[i]+=a[step];
if(tmp) return true;
}
return false;
}
int main()
{
scanf("%d",&m); int i;
for(i=1;i<=m;++i)
{
scanf("%d",len+i);
sum+=len[i];
}
sort(len+1,len+m+1);
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%d",a+i);
sort(a+1,a+n+1);
for(i=1;i<=n;++i) s[i]=s[i-1]+a[i];
int l=0,r=n+1,mid;
while(l<r)
{
mid=(l+r)>>1; tmp=s[mid];
if(dfs(mid)) l=mid+1;
else r=mid;
}
printf("%d",l-1);
return 0;
}