1082: [SCOI2005]栅栏

链接

思路

　　二分+搜索+剪枝。

　　首先二分一个答案，表示最多可以切出x块。（一个结论：切出的一定是从较小的前x块。如果一个木材可以满足很多个需要的木材，那么切出最小的，就意味着以后再选时的机会更多。）

　　然后暴力搜索前x块分别由哪个木材切出。

　　剪枝1：如果所有提供的木材加起来也不能满足需要的木材，直接跳过

　　剪枝2：记录一下浪费掉的木材（即一块木材切掉了一些后，剩下的木材中连最小的也切不出了的），如果提供的木材总量-浪费掉<当前所有的木材需要的，直接跳过。

　　剪枝3：当前需要的和下一块需要的木材是一样长的，那么不必从第一块开始搜索了，直接从上次搜索到的地方开始。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 const int N = ;

 int n,m,rest,tot;

 int a[N],b[N],c[N],sum[N];

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x * f;

 }

 bool dfs(int now,int s) { // 当前需要的木材，从给出的木材中第s个开始

     if (!now) return true;

     if (rest+sum[now] > tot) return false; // 剪枝2

     for (int i=s; i<=m; ++i) { // 枚举所有给出的木材

         if (c[i] >= b[now]) { // 当前木材可以切出需要的

             c[i] -= b[now]; //-

             if (c[i] < b[]) rest += c[i];

             if (b[now]==b[now-]) {

                 if (dfs(now-,i)) return true;

             }

             else {if (dfs(now-,)) return true;} // 剪枝3

             if (c[i] < b[]) rest -= c[i];

             c[i] += b[now]; // -

         }

     }

     return false;

 }

 bool check(int x) {

     for (int i=; i<=m; ++i) c[i] = a[i];

     rest = ;

     return dfs(x,);

 }

 int main() {

     m = read();

     for (int i=; i<=m; ++i) a[i] = read(),tot += a[i];

     sort(a+,a+m+);

     n = read();

     for (int i=; i<=n; ++i) b[i] = read();

     sort(b+,b+n+);

     for (int i=; i<=n; ++i) sum[i] = sum[i-] + b[i];

     while (sum[n] > tot) n--; // 剪枝1

     int L = ,R = n,ans; // L有等于0的情况！

     while (L <= R) {

         int mid = (L + R) / ;

         if (check(mid)) L = mid + ,ans = mid;

         else R = mid - ;

     }

     cout << ans <<'\n';

     return ;

 }