Home > Old Blog Posts > USACO 2.1.4 Healthy Holsteins

USACO 2.1.4 Healthy Holsteins


一开始想复杂了……

后来一看范围:1<=g<=15,我晕,2^15=32768,爆搜吧

此题超时者神牛

代码:

/*
ID: dementr1
PROG: holstein
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“holstein.in”);
ofstream fout(“holstein.out”);
int counter=0;
int least[30],vitamin[20][30],v,g;
char list[300000][15];
bool solved=false;
void init()
{
int i,j;
fin>>v;
for(i=0;i<v;i++) fin>>least[i];
fin>>g;
for(i=0;i<g;i++)
for(j=0;j<v;j++) fin>>vitamin[i][j];
memset(list,0,sizeof(list));
}
void comb(int n, int r)
{
int i,k,j;
for(i=0;i<r;i++)
list[counter][i]=i+1;
counter++;
for(;;)
{
bool have=false;
for(k=r-1;k>=0;k–)
{
if(list[counter-1][k]+1<=n)
{
bool flag=true;
for(j=0;j<r;j++)    if(j!=k&&list[counter-1][k]+1==list[counter-1][j])
{
flag=false;
break;
}
if(flag==false) continue;
list[counter][k]=list[counter-1][k]+1;
for(i=k+1;i<r;i++) list[counter][i]=list[counter][i-1]+1;
for(i=0;i<k;i++) list[counter][i]=list[counter-1][i];
counter++;
have=true;
break;
}
}
if(!have) break;
}
}
void work()
{
int i,j,k,tmp[30]={};
for(i=1;i<=g;i++) comb(g,i);
for(i=0;i<counter;i++)
{
memset(tmp,0,sizeof(tmp));
for(j=0;j<g;j++)
if(list[i][j]!=0)
for(k=0;k<v;k++)
tmp[k]+=vitamin[list[i][j]-1][k];
bool flag=true;
for(j=0;j<v;j++)
if(tmp[j]<least[j])
{
flag=false;
break;
}
if(flag)
{
int sum=0;
for(j=0;j<g;j++) if(list[i][j]!=0) sum++;
fout<<sum<<” “;
for(j=0;j<sum-1;j++) fout<<(int)list[i][j]<<” “;
fout<<(int)list[i][sum-1]<<endl;
break;
}
}
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: