90分求调
查看原帖
90分求调
1498139
victor_oier楼主2024/10/20 23:52

90pts,求调

#include<bits/stdc++.h>
using namespace std;
int v,a[30],b[30][30],vis[30],g,ans=2e9;
int f[30],s[30];
bool check(){
	for(int i=1;i<=v;i++){
		if(vis[i]<a[i]) return false;
	}
	return true;
}
void dfs(int cnt,int sum){
	if(cnt==g+1){
		if(ans>sum&&check()){
			ans=sum;
			for(int i=1;i<=30;i++) s[i]=f[i];
			//每个饲料的编号 
		}
		return;
	}
	for(int i=1;i<=v;i++) vis[i]+=b[cnt][i];
	f[cnt]=1;//判断选或者不选 
	dfs(cnt+1,sum+1);
	f[cnt]=0;
	for(int i=1;i<=v;i++) vis[i]-=b[cnt][i];
	//vis[i]表示在当前方案中没中维他命的数量 
	dfs(cnt+1,sum);
}
int main(){
	cin>>v;
	for(int i=1;i<=v;i++) cin>>a[i];
	cin>>g;
	for(int i=1;i<=g;i++){
		for(int j=1;j<=v;j++){
			cin>>b[i][j];
		}
	} 
	dfs(1,0);
	cout<<ans<<" ";
	for(int i=1;i<=30;i++){
		if(s[i]==1) cout<<i<<" ";
	}
	return 0; 
}

在线等(;´д`)ゞ

2024/10/20 23:52
加载中...