首页 > 代码库 > 洛谷P1460 健康的荷斯坦奶牛 Healthy Holsteins
洛谷P1460 健康的荷斯坦奶牛 Healthy Holsteins
题目描述
农民JOHN以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。
给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。
维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。
输入输出格式
输入格式：第1行：一个整数V(1<=V<=25)，表示需要的维他命的种类数。
第2行：V个整数(1<=每个数<=1000)，表示牛每天需要的每种维他命的最小量。
第3行：一个整数G(1<=G<=15)，表示可用来喂牛的饲料的种数。
下面G行，第n行表示编号为n饲料包含的各种维他命的量的多少。
输出格式：输出文件只有一行，包括
牛必需的最小的饲料种数P
后面有P个数，表示所选择的饲料编号（按从小到大排列）。
如果有多个解，输出饲料序号最小的（即字典序最小）。
输入输出样例
输入样例#1：
4100 200 300 400350 50 50 50200 300 200 300900 150 389 399
输出样例#1：
2 1 3
说明
USACO 2.1
翻译来自NOCOW
又是一道奶牛题。
暴搜就能过
/*by SilverN*/#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<vector>using namespace std;const int mxn=30;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int rans=1e9;int ans[mxn];int n,v[mxn],g,w[mxn][mxn];int now[mxn],cpy[mxn];bool check(){// for(int i=1;i<=n;i++)printf("%d ",now[i]);// printf("\n"); for(int i=1;i<=n;i++) if(now[i]<v[i])return 0; return 1;}void DFS(int res,int pos){ if(res>=rans)return; if(check()){ rans=res; memcpy(ans,cpy,sizeof ans); return; }// printf("%d %d\n",res,pos); for(int i=pos;i<=g;i++){ for(int j=1;j<=n;j++)now[j]+=w[i][j]; cpy[res]=i; DFS(res+1,i+1); for(int j=1;j<=n;j++)now[j]-=w[i][j]; } return;}int main(){ n=read(); int i,j; for(i=1;i<=n;i++)v[i]=read(); g=read(); for(i=1;i<=g;i++) for(j=1;j<=n;j++) w[i][j]=read(); DFS(1,1); printf("%d ",rans-1); for(i=1;i<rans;i++)printf("%d ",ans[i]); return 0;}
洛谷P1460 健康的荷斯坦奶牛 Healthy Holsteins
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。