[SCOI2005]栅栏（贪心+二分+dfs）
P2329 [SCOI2005]栅栏
题目描述
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为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

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<deque>
#include<queue>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=1e4+1;
const int mod=1e9+7;
using namespace std;
int sum,m,n,a[maxn],b[maxn],c[maxn],waste,mid,le,ri,ans;
bool dfs(int x,int last)
{
    bool flag;
    if(waste>sum-c[mid])return false;
    if(x==0)return true;
    for(int i=last;i<=m;i++)
    {
        if(a[i]>=b[x])
        {
            a[i]-=b[x];
            if(a[i]<b[1])waste+=a[i];
            if(b[x-1]==b[x])flag=dfs(x-1,i);
            else flag=dfs(x-1,1);
            if(a[i]<b[1])waste-=a[i];
            a[i]+=b[x];
            if(flag)return true;
        }
    }
    return false;
}
int main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i],sum+=a[i];
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>b[i];
    sort(a+1,a+m+1);
    sort(b+1,b+1+n);
    c[0]=0;
    for(int i=1;i<=n;i++)
        c[i]=c[i-1]+b[i];
    while(c[n]>sum)n--;
    ri=n;
    while(le<=ri)
    {
        waste=0;
        mid=(le+ri)>>1;
        if(dfs(mid,1))
            ans=mid,le=mid+1;
        else ri=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}

详细题解