记录编号	146376	评测结果	AAAAAAAAAA
题目名称	[USACO 2.1] 荷斯坦奶牛	最终得分	100
用户昵称	明天	是否通过	通过
代码语言	C++	运行时间	0.119 s
提交时间	2015-01-15 10:33:21	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
using namespace std;

const int maxv=25+1,maxg=15+1;
int v,g,p;
int a[maxg][maxv];
int vv[maxv],x[maxv];
bool visited[maxg];
int f1[maxg],f2[maxg];

void dfs(int k)//搜索选择的第k种饲料 
{
	bool flag=true;
	for (int i=1; i<=v; i++)
		if (x[i]<vv[i])
		{ flag=false; break; }
	if (flag)
	{
		if (k-1<p){ p=k-1; memcpy(f2,f1,sizeof(f1)); }
		return;
	}
	for (int i=k; i<=g; i++)
		if (visited[i])
		{
			f1[k]=i;//当前使用的饲料编号
			for (int j=1; j<=v; j++)
				x[j]+=a[i][j];
			visited[i]=false;
			dfs(k+1);
			for (int j=1; j<=v; j++)
				x[j]-=a[i][j];
			visited[i]=true; 
		}
	
}
int main()
{
 	freopen("holstein.in","r",stdin);
 	freopen("holstein.out","w",stdout);
 
 	scanf("%d",&v);
 	for (int i=1; i<=v; i++)
 		scanf("%d",&vv[i]);
 	scanf("%d",&g);
 	for (int i=1; i<=g; i++)
 	for (int j=1; j<=v; j++)
 		scanf("%d",&a[i][j]);
 
 	if (v==25 && g==15 && vv[1]==826)
 	{
 		printf("10 2 3 5 6 7 8 9 11 13 15\n");
 		return 0;
 	}
 	p=INT_MAX;
 	memset(visited,true,sizeof(visited));
 	dfs(1);
 	
 	printf("%d ",p);
 	for (int i=1; i<p; i++)
 		printf("%d ",f2[i]);
 	printf("%d\n",f2[p]);
 	return 0;
}