社区讨论

用了7个优化还是54pts 萌新求助

P1120[CERC 1995] 小木棍参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo9bdo9l
此快照首次捕获于
2023/10/28 08:38
2 年前
此快照最后确认于
2023/10/28 08:38
2 年前
查看原帖
CPP
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int n, a[100], mem[100];
bool cmp(int x, int y) {
	return x > y;
}
bool bo[100], ans;
bool dfs(int le, int cnt, int lim, int now) {
	if (ans)return 1;//优化
	if (!le) {
		if (cnt == n) {
			ans = 1;
			return 1;
		}
		else if (!dfs(lim, cnt, lim, 1))return 0;//优化
		return 1;
	}
	for (int i = now; i <= n; i++) {//i=now 优化
		if (le >= a[i] && (!bo[i])) {
			bo[i] = 1;
			if (!dfs(le - a[i], cnt + 1, lim, i + 1)) {
				if (le == lim) {
					bo[i] = 0;
					return 0;//优化
				}
				bo[i] = 0;
				i = mem[a[i]];//优化
			}
		}
	}
	return 0;
}
int main() {
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	sort(a + 1, a + n + 1, cmp);//优化
	for (int i = 1; i <= n; i++) {
		if (a[i] != a[i + 1]) {
			mem[a[i]] = i;//优化
		}
	}
	for (int i = a[1]; i <= sum; i++) {
		dfs(i, 0, i, 1);
		if (ans) {
			cout << i << endl;
			return 0;
		}
	}
}

回复

0 条回复,欢迎继续交流。

正在加载回复...