记录编号	111598	评测结果	AAAAAAAAAA
题目名称	[USACO 2.1] 荷斯坦奶牛	最终得分	100
用户昵称	chs	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-07-13 17:35:31	内存使用	0.44 MiB

#include<iostream>
#include<fstream>
using namespace std;
const int maxn=30;
const int maxx=1010;
int n,m;
int need[maxx];
int v[maxn][maxx];
int st[maxx]={0};
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)||(t==n)&&(p-1<=mi&&add>tot))
	{
		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++)
		{
			G[p++]=i;
			seek(i);
			p--;
		}
	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;
}