悬关求助,暴力为何过不了样例?
  • 板块P1120 小木棍
  • 楼主rainygame
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/4/21 07:12
  • 上次更新2023/10/23 17:56:25
查看原帖
悬关求助,暴力为何过不了样例?
804607
rainygame楼主2023/4/21 07:12

RT。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 66

int n;
int a[MAXN], h[MAXN];
bitset<MAXN> vis;

bool dfs(int ans, int step, int res, int las){
	if (step == n) return res;
	
	bool flag = false;
	step++;
	for (int i=n; i>=1; i--){
		if (vis.test(i) || a[i] > res || a[i] > las) continue;
		vis.set(i);
		if (a[i] == res) flag |= dfs(ans, step, ans, ans);
		else flag |= dfs(ans, step, res-a[i], a[i]);
		if (flag) return true;
		vis.reset(i);
	}
	
	return false;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i=1; i<=n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	
	for (int i=1; ; i++){
		if (dfs(i, 0, i, i)){
			cout << i;
			return 0;
		}
	}
	
	return 0;
}

目前还没有剪枝。

2023/4/21 07:12
加载中...