USER: tianbing tianbing [tbbd4261]
TASK: holstein
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 2932 KB]
Test 2: TEST OK [0.000 secs, 2932 KB]
Test 3: TEST OK [0.022 secs, 2932 KB]
Test 4: TEST OK [0.022 secs, 2932 KB]
Test 5: TEST OK [0.011 secs, 2932 KB]
Test 6: TEST OK [0.000 secs, 2932 KB]
Test 7: TEST OK [0.000 secs, 2932 KB]
Test 8: TEST OK [0.022 secs, 2932 KB]
Test 9: TEST OK [0.032 secs, 2932 KB]
Test 10: TEST OK [0.022 secs, 2932 KB]
All tests OK.
Your program ('holstein') produced all correct answers! This is your
submission #4 for this problem. Congratulations!
一定要審題，剛開始把題目看錯了。
直接搜索所有情況，用cnt和ans[]分別紀錄最小的種數及與最小種數對應的狀態
DFS可以保證cnt相等時先搜到的比后搜到的字典序靠前
/*
ID:tbbd4261
PROG:holstein
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<climits>
#include<cstring>
using namespace std;
ifstream fin("holstein.in");
ofstream fout("holstein.out");
int need[26]={0},
amount[16][26]={0};
bool f[16]={0},ans[16]={0};
int now[26]={0};
int n,i,g,j,mmin=INT_MAX,cnt=INT_MAX;
int check()
{
int sum=0;
memset(now,0,sizeof now);
for(int i=1; i<=g; i++)
{ if(f[i])
for(int j=1; j<=n; j++)
now[j]+=amount[i][j];
}
bool flag=1;
for(int i=1; i<=n&&flag; i++)
{
sum+=now[i];
if(now[i]<need[i]){ flag=0; break; }
}
if(flag)return sum; //sum是多余的，原來以為要求和的 直接return falg；
return 0;
}
void dfs(int deep,int count)
{
if(deep>g)return ;
int s;
f[deep]=1;
s=check();
if(s>0&&count+1<cnt)
{
cnt=count+1;
for(i=1; i<=g; i++)
ans[i]=f[i];
}
dfs(deep+1,count+1);
f[deep]=0;
dfs(deep+1,count);
}
void input()
{
fin>>n;
for(i=1; i<=n; i++)
fin>>need[i];
fin>>g;
for(i=1; i<=g; i++)
for(j=1; j<=n; j++)
fin>>amount[i][j];
}
void solve()
{
dfs(1,0);
fout<<cnt;
for(int i=1; i<=g; i++)
if(ans[i])fout<<' '<<i;
fout<<endl;
}
int main()
{
input();
solve();
//system("pause");
return 0;
}