dfs30求调
查看原帖
dfs30求调
1272259
cgxd楼主2024/11/30 16:19
#include<bits/stdc++.h>
using namespace std;
int v, g, p = 50, fd[35][35];
array<int, 35> need;
typedef tuple<bitset<35>, array<int, 35>, int, int> tpl;
void add(tpl &t, bool bl, int k){
	bitset<35> &bs = get<0>(t);
	array<int, 35> &cur = get<1>(t);
	int &sum = get<2>(t), &cnt = get<3>(t);
	cnt += bl;
	sum = (sum << 1) | (bs[k] = bl);
	if(bl) for(int i = 1; i <= v; ++i) cur[i] += fd[k][i];
}bool check(tpl t){
	array<int, 35> cur = get<1>(t);
	return cur >= need;
}tpl ans, start;
void dfs(tpl cur, int k){
	if(check(cur)){
		if(get<3>(cur) < get<3>(ans)) ans = cur;
		if(k < g) get<2>(cur) <<= g - k;
		if(get<3>(cur) == get<3>(ans) and get<2>(cur) < get<2>(ans))
			return;
	}if(k == g + 1) return;
	tpl nxt1 = cur, nxt2 = cur;
	add(nxt1, 1, k);
	dfs(nxt1, k + 1);
	add(nxt2, 0, k);
	dfs(nxt2, k + 1);
}signed main(){
	scanf("%d", &v);
	for(int i = 1; i <= v; ++i) scanf("%d", &need[i]);
	scanf("%d", &g);
	for(int i = 1; i <= g; ++i) for(int j = 1; j <= v; ++j) scanf("%d", &fd[i][j]);
	get<3>(ans) = g + 2;
	dfs(start, 0);
	printf("%d", get<3>(ans));
	for(int i = 1; i <= g; ++i) if(get<0>(ans)[i]) printf(" %d", i);
	return 0;
}
2024/11/30 16:19
加载中...