usaco_Healthy Holsteins_dfs

2019-11-14 09:55:53

字體：大中小

來源：轉載

供稿：網友

題目描述

農民JOHN以擁有世界上最健康的奶牛為傲。他知道每種飼料中所包含的牛所需的最低的維他命量是多少。請你幫助農夫喂養他的牛，以保持它們的健康，使喂給牛的飼料的種數最少。

給出牛所需的最低的維他命量，輸出喂給牛需要哪些種類的飼料，且所需的飼料劑量最少。

維他命量以整數表示，每種飼料最多只能對牛使用一次，數據保證存在解。

思路

暴力搜索每一個點，選或不選，如果當前個數比最小個數要小就搜下去，不然就退出 O(2^m)

/*ID: a1192631PROG: holsteinLANG: C++*/#include <stdio.h>int a[26][26];int f[26],fl[26],ll[26];int n,m,ans=0,min=1000;int dfs(int dep){ if (dep>m) return 0; int t=0; for (int i=1;i<=n;i++) { f[i]-=a[dep][i]; if (f[i]<=0) t++; } fl[dep]=1; ans++; if (t==n) { for (int i=1;i<=m;i++) ll[i]=fl[i]; min=ans; } if (ans+1<min) dfs(dep+1); fl[dep]=0; ans--; for (int i=1;i<=n;i++) { f[i]+=a[dep][i]; } dfs(dep+1);}int main(){ freopen("holstein.in", "r", stdin); freopen("holstein.out", "w", stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&f[i]); scanf("%d",&m); for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); dfs(1); printf("%d",min); for (int i=1;i<=m;i++) if (ll[i]==1) printf(" %d",i); printf("/n");}

上一篇：1034. Head of a Gang (30)

下一篇：Elaxia的路線 SDOI2009 最短路