「SCOI2005」栅栏

传送门

Luogu

解题思路

我们有很显然的这样一条贪心思路：

首先满足长度短的木板，因为如果可以满足长的也肯定可以满足短的，而且可能满足更多。

那么我们就会有这样的思路：枚举一条木板由哪条木板切割而来。

然后我们就可以考虑一堆剪枝了：

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

细节注意事项

爆搜题，你们懂得。。。

参考代码

#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\)

巴特西

「SCOI2005」栅栏

解题思路

细节注意事项

参考代码

最新文章

热门文章