50pts,求助QWQ
查看原帖
50pts,求助QWQ
600112
_HHJ楼主2023/10/27 11:56
// 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 debug(x) std::cout << #x << "=" << x << '\n';
#define int long long
constexpr int N = 30;
int v,vs[N];
int g,gs[N][N],sum[N],tmp[N];
int ans_cnt,ans[N];
bool check(){
	for (int i = 1 ; i <= v ; ++ i ) {
		if(sum[i] < vs[i]) return false;
	}
	return true;
}

void print_arr(int a[],int n) {
	for (int i = 1 ; i <= n ; ++ i ) std::cout << a[i] << " \n"[i == n];
}

void dfs(int idx,int cnt){
	//print_arr(sum,v);
	//debug(cnt);
	//debug(idx);
	if(idx == v + 1) {
		if(cnt < ans_cnt && check()){
			ans_cnt = cnt - 1;
			for (int i = 1 ; i <= v ; ++ i ) ans[i] = tmp[i];
			//print_arr(sum,v);
			return;
		}
		return;
	}
	for (int i = 1 ; i <= v ; ++ i ) sum[i] += gs[idx][i];
	tmp[cnt] = idx;
	dfs(idx + 1, cnt + 1);
	tmp[cnt] = 0;
	for (int i = 1 ; i <= v ; ++ i ) sum[i] -= gs[idx][i];
	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 = 1e9;
	dfs(1,1);
	std:: cout << ans_cnt << ' ';
	for (int i = 1 ; i <= ans_cnt ; ++ i) std::cout << ans[i] << ' ';
	return 0;
}
2023/10/27 11:56
加载中...