比赛 20140713下午练习 评测结果 AAAWAWWWWW
题目名称 荷斯坦奶牛 最终得分 40
用户昵称 chs 运行时间 0.010 s
代码语言 C++ 内存使用 0.44 MiB
提交时间 2014-07-13 17:08:17
显示代码纯文本
#include<iostream>
#include<fstream>
using namespace std;
const int maxn=30;
const int maxx=1010;
int n,m;//n->营养种类//m->饲料种类
int need[maxx];
int v[maxn][maxx];
int st[maxx];
int G[maxn],p=0;
int mi=maxx,add=maxx;
int F[maxn],k=0;
void seek(int x)
{
	int i,j,t=0,tot=0;
	for(i=1;i<=n;i++) st[i]+=v[x][i];
	for(i=1;i<=n;i++) if(st[i]>=need[i]) t++;
	if(t==n) for(i=0;i<p;i++) tot+=G[i];
	if(t==n&&p-1<=mi)
	{
		mi=p-1;
		add=tot;
		for(i=0;i<p;i++) F[i]=G[i];
		k=p;
	}
	else
		for(i=x+1;i<=m;i++)
		{
			for(j=1;j<=n;j++) st[j]+=v[i][j];
			G[p++]=i;
			seek(i);
			p--;
			for(j=1;j<=n;j++) st[j]-=v[i][j];
		}
	for(i=1;i<=n;i++) st[i]-=v[x][i];
}
int main()
{
	freopen("holstein.in","r",stdin);
	freopen("holstein.out","w",stdout);
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++) cin>>need[i];
	cin>>m;
	for(i=1;i<=m;i++) for(j=1;j<=n;j++) cin>>v[i][j];
	//================================================
	for(int i=1;i<=m;i++){G[p++]=i;seek(i);p--;}
	//================================================
	cout<<k<<" ";
	for(i=0;i<k;i++) cout<<F[i]<<" ";
	cout<<endl;
	return 0;
}