社区讨论
用了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 条回复,欢迎继续交流。
正在加载回复...