holstein.cpp

USACO Section 2.1的全部AC的代码 OIer专用.

/*
NAME:lemon_c1
LANG:C++
PROG:holstein
*/
#include<fstream>
using namespace std;
ifstream cin("holstein.in");
ofstream cout("holstein.out");
int n,m;
int v[26];
int f[16][26];
bool x[16];
int solutions[16];
int cv[26];
int best;
int bsum=1000000;
int csum=0;
int ccount=0;
void swap(int &t1,int &t2)
{
	int t=t1;
	t1=t2;
	t2=t;
}
bool check(void)
{
	for(int i=1;i<=n;i++)
		if(cv[i]<v[i])return false;
	return true;
}
void dfs(int layer);
void output(void)
{
	cout<<best;
	for(int i=1;i<=best;i++)
		cout<<' '<<solutions[i];
	cout<<endl;
}
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>v[i];
	cin>>m;
	best=m+1;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			cin>>f[i][j];
	dfs(1);
	output();
	return 0;
}
void dfs(int layer)
{
	if(check())
	{
		if(ccount<best)
		{
			best=ccount;
			int cnt=1;
			for(int i=1;i<=layer;i++)
				if(x[i])solutions[cnt++]=i;
			bsum=csum;
		}
		else if(ccount==best && csum<bsum)
		{
			int cnt=1;
			for(int i=1;i<=layer;i++)
				if(x[i])solutions[cnt++]=i;
			bsum=csum;
		}
		return;
	}
	if(layer==m+1)return;
	dfs(layer+1);
	x[layer]=true;
	ccount++;
	for(int i=1;i<=n;i++)
		cv[i]+=f[layer][i];
	csum+=layer;
	dfs(layer+1);
	csum-=layer;
	ccount--;
	x[layer]=false;
	for(int i=1;i<=n;i++)
		cv[i]-=f[layer][i];
}