「SCOI2005」栅栏

发表于 更新于 分类于

题目链接

这道题的正解竟然就是 dfs +剪枝...
可以把题目理解成用木板去塞木材，最多塞多少个。

先将不可能塞的不板和不可能被塞的木材排除。

二分答案最多能塞多少个木板，搜索每个木材塞到哪个板，显然用更小的木板来塞一定不会更差。

记录前 mid 个木板的和，总的木材的和。
搜索的时候随时减去不能再被塞的木材。

如果某个时候\(sum[mid]+w\ge S\)则 return
如果木板大小相同，就直接从上一次塞的位置继续，因为我们应该让这些木板只能按某种顺序塞来减少状态数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, m, mid, S, a[N], b[N], sum[N], lst[N];
bool flg;

void dfs(int x, int p, int w) {
	if (x == 0) return (void)(flg = 1);
	while (a[p] < b[1] && p <= n) w += a[p], p++;
	if (p > n || w + sum[mid] > S || flg) return;
	int t = p;
	if (x != mid && b[x] == b[x + 1]) t = lst[x + 1];
	for (int i = t; i <= n; i++) if (a[i] >= b[x]) {
		lst[x] = i;
		a[i] -= b[x];
		dfs(x - 1, p, w);
		a[i] += b[x];
		if (flg) return;
	}
}

int main() {
    scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
	sort(a + 1, a + n + 1);
	sort(b + 1, b + m + 1);
	while (b[m] > a[n]) m--;
	int tot = 0;
	for (int i = 1; i <= n; i++) if (a[i] >= b[1]) a[++tot] = a[i];
    n = tot;
    for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + b[i];
	for (int i = 1; i <= n; i++) S += a[i];
	int l = 1, r = m, ans = 0;
	while (l <= r) {
		mid = (l + r) >> 1;
		flg = 0;
		dfs(mid, 1, 0);
		if (flg) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}

```