「SCOI2005」栅栏

传送门
Luogu

解题思路

我们有很显然的这样一条贪心思路：
首先满足长度短的木板，因为如果可以满足长的也肯定可以满足短的，而且可能满足更多。
那么我们就会有这样的思路：枚举一条木板由哪条木板切割而来。
然后我们就可以考虑一堆剪枝了：

1. 如果当前长木板长度\(-\)浪费的木板长度\(<\)所需要的木板长度，剪掉；
   
2. 如果当前需要满足的木板和前一块长度相同，那么就去dfs前一块，因为如果满足不了第 \(i\) 块，那么第 \(i-1\) 块也一定不行 。
3. 二分答案减少搜索范围

细节注意事项

• 爆搜题，你们懂得。。。

参考代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
    s = f ? -s : s;
}

const int _ = 51;
const int __ = 1002;

int m, sa, a[_];
int n, b[__], sb[__];
int aa[_], mid, s;

inline int dfs(int x, int last) {
    if (x <= 0) return 1;
    if (sa - s < sb[mid]) return 0;
    for (rg int i = last; i <= m; ++i) {
        if (aa[i] >= b[x]) {
            aa[i] -= b[x];
            if (aa[i] < b[1]) s += aa[i];
            if (b[x] == b[x - 1]) {
                if (dfs(x - 1, i)) return 1;
            } else if (dfs(x - 1, 1)) return 1;
            if (aa[i] < b[1]) s -= aa[i];
            aa[i] += b[x];
        }
    }
    return 0;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    read(m);
    for (rg int i = 1; i <= m; ++i) read(a[i]), sa += a[i];
    read(n);
    for (rg int i = 1; i <= n; ++i) read(b[i]);
    sort(b + 1, b + n + 1);
    for (rg int i = 1; i <= n; ++i) sb[i] = sb[i - 1] + b[i];
    while (sb[n] > sa) --n;
    int l = 0, r = n;
    while (l < r) {
        memcpy(aa, a, sizeof (int) * (m + 1)), s = 0;
        mid = (l + r + 1) >> 1;
        if (dfs(mid, 1)) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}

完结撒花 \(qwq\)