usaco_Healthy Holsteins_dfs

2019-11-14 09:03:42

字体：大中小

来源：转载

供稿：网友

题目描述

农民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");}

上一篇：368. Largest Divisible Subset -Medium

下一篇：GridView绑定数据的方法