比赛 20160708BDFS 评测结果 AAAAAAAAAA
题目名称 荷斯坦奶牛 最终得分 100
用户昵称 Ostmbh 运行时间 0.010 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2016-07-08 09:19:12
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int v,g;
int A[26];
int F[16][26];
int ans[16];
struct T{
	int c[26];
	int a[16];
};
int minn=0x7fffffff;
void dfs(int last,int mi,T c){
	int ok=1;
	for(int i=1;i<=v;i++)
		if(c.c[i]<A[i]){
			ok=0;
			break;
		}
	if(ok&&mi<minn){
		minn=mi;
		for(int i=1;i<=mi;i++)
			ans[i]=c.a[i];
		return ;
	}
	if(!ok&&mi>minn)
		return ;
	for(int j=last+1;j<=g;j++){
		T f=c;
		for(int i=1;i<=v;i++)
			f.c[i]+=F[j][i];
			f.a[mi+1]=j;
			dfs(j,mi+1,f);
	}
}
int main(){
	freopen("holstein.in","r",stdin);
	freopen("holstein.out","w",stdout);
	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>>F[i][j];
	T e;
	memset(e.c,0,sizeof(e.c));
	dfs(0,0,e);
	cout<<minn<<' ';
	for(int i=1;i<=minn;i++)
		cout<<ans[i]<<' ';
return 0;
}