holstein.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: holstein
LANG: C++
*/
#include <stdio.h>
#include <string>
using std::string;
bool hash[16]={0};
int need[26];
int has[16][26];
int fuck[26];


int G,V;
int length;
int minlength=200;
string answer,maxanswer="";

void getAns()
{
	memset(fuck,0,sizeof(fuck));
	answer="";
	length=0;
	for(int a=1;a<=G;a++)
		if(hash[a])
		{
			length++;
			answer=answer+(char)(a+(int)'0');
			for(int b=1;b<=V;b++)
				fuck[b]+=has[a][b];
		}
	bool fuckfuck=true;
	for(int a=1;a<=V;a++)
		fuckfuck=fuckfuck&&(fuck[a]>=need[a]);
	if((length<minlength||(length==minlength&&(answer<maxanswer)))&&fuckfuck)
	{
		maxanswer=answer;
		minlength=length;
	}
}

void searchit(int n)
{
	if(n==G+1)
		getAns();
	else
	{
		hash[n]=!hash[n];
		searchit(n+1);
		hash[n]=!hash[n];
		searchit(n+1);
	}
}

int main()
{
	freopen("holstein.in","r",stdin);
	freopen("holstein.out","w",stdout);
	scanf("%d",&V);
	for(int a=1;a<=V;a++)
		scanf("%d",&need[a]);
	scanf("%d",&G);
	for(int a=1;a<=G;a++)
		for(int b=1;b<=V;b++)
			scanf("%d",&has[a][b]);
	searchit(1);
	printf("%d",minlength);
	for(int a=1;a<=maxanswer.length();a++)
		printf(" %d",((int)maxanswer.data()[a-1]-(int)'0'));
	printf("\n");
	return 0;
}