USACO 2.1.4

 1 /*
 2 ID: weitong4
 3 LANG: C++
 4 TASK: holstein
 5 */
 6 #include<stdio.h>
 7 #include<string.h>
 8 #define v_max 25+5
 9 #define g_max 15+5
10 
11 int v,g;
12 int a[v_max],b[g_max][v_max];
13 int ans[v_max],min,res[v_max];
14 bool vis[v_max];
15 
16 void dfs(int cur,int cnt,int sol,int temp[]){
17     if(sol>=v){
18         if(cnt<min){
19             min=cnt;
20             for(int i=0;i<cnt;i++){
21                 ans[i]=res[i];
22             }
23         }
24         return;
25     }
26     for(int i=cur;i<=g;i++){
27         if(vis[i]){
28             continue;
29         }
30         vis[i]=true;
31         res[cnt]=i;
32         int count=0;
33         int t[v_max];
34         for(int j=1;j<=v;j++){
35             t[j]=temp[j];
36             if(temp[j]<=0){
37                 continue;
38             }
39             t[j]=temp[j]-b[i][j];
40             if(t[j]<=0){
41                 count++;
42             }
43         }
44         dfs(i+1,cnt+1,sol+count,t);
45         vis[i]=false;
46     }
47 }
48 
49 int main(){
50     freopen("holstein.in","r",stdin);
51     freopen("holstein.out","w",stdout);
52     while(~scanf("%d",&v)){
53         memset(vis,false,sizeof(vis));
54         for(int i=1;i<=v;i++){
55             scanf("%d",&a[i]);
56         }
57         scanf("%d",&g);
58         for(int i=1;i<=g;i++){
59             for(int j=1;j<=v;j++){
60                 scanf("%d",&b[i][j]);
61             }
62         }
63             min=999999;
64         dfs(1,0,0,a);
65         printf("%d",min);
66         for(int i=0;i<min;i++){
67             printf(" %d",ans[i]);
68         }
69         puts("");
70     }
71 }