萌新刚学 搜索, 7 RE 求注
查看原帖
萌新刚学 搜索, 7 RE 求注
600112
_HHJ楼主2023/11/4 17:22
// Problem: P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1460
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define int long long

constexpr int N = 3000;
int v,vs[N];
int g,gs[N][N],sum[N],tmp[N];
int ans_cnt,ans[N];

bool check(int x){
	for (int i = 1 ; i <= v ; ++ i) {
		int res = 0;
		for (int j  = 1 ; j <= x ; ++ j ) {
			res += gs[tmp[j]][i];
		}
		if(res < vs[i]) return false;
	}
	return true;
}

void dfs(int idx,int cnt){
	if(idx == v + 1) {
		if(cnt - 1 < ans_cnt && check(cnt - 1)){
			ans_cnt = cnt - 1;
			for (int i = 1 ; i <= ans_cnt ; ++ i ) ans[i] = tmp[i];
		}
		return;
	}
	tmp[cnt] = idx;
	dfs(idx + 1, cnt + 1);
	tmp[cnt] = 0;
	dfs(idx + 1,cnt);
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cout.tie(0); std::cin.tie(0);
	std:: cin >> v;
	for (int i = 1 ; i <= v ; ++ i ) std::cin >> vs[i];
	std:: cin >> g;
	for (int i = 1 ; i <= g ; ++ i ) {
		for (int j = 1 ; j <= v ; ++ j) {
			std:: cin >> gs[i][j];
		}
	}
	ans_cnt = g ;
	dfs(1,1);
	std:: cout << ans_cnt << ' ';
	for (int i = 1 ; i <= ans_cnt ; ++ i) std::cout << ans[i] << ' ';
	return 0;
}
2023/11/4 17:22
加载中...