usaco_holstein.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:holstein
LANG:C++
*/
//#include <iostream>
#include <fstream>
#include <memory>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin ("holstein.in");
ofstream cout ("holstein.out");  
int a[15][25];
int s[25],n[25];
bool used[15];
bool now[15];
int v,g,minv,minvv;

bool match_ok()
{
	int i,j;
     bool flag=true;
	 memset(n,0,sizeof(n));
	 for( i=0;i<g;i++)
		 {
			 if(used[i])
				 for( j=0;j<v;j++)
				     n[j]+=a[i][j];
		 }
     for( i=0;i<v;i++)
     {
         if(n[i]<s[i]) 
         {flag=false;  break;}
     }
     return flag;
}
void searcha(int t)
{
     int i,j,k;
     if(minv<minvv && t<g)
     {
		used[t]=true;
		minv++;
		if(match_ok())
		{
			if(minv<minvv) 
			{
				minvv=minv;
				memcpy(now,used,sizeof(used));
			}
		}
		else searcha(t+1);
		minv--;
		used[t]=false;
		searcha(t+1);
     }     
} 

int main()
{
    int i,j,k;
    cin>>v;
    for(i=0;i<v;i++) cin>>s[i];
    cin>>g;
    for(j=0;j<g;j++)
       for(i=0;i<v;i++) cin>>a[j][i];
	minv=0;
	minvv=g+1;
    memset(used,false,sizeof(used));   
    memset(n,0,sizeof(n));
	searcha(0);
    cout<<minvv;
    for(i=0;i<g;i++)
      if(now[i]) cout<<' '<<i+1;
    cout<<endl;
  //  system("PAUSE");
    return 0;
}