tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 计算机软件及应用 >>

USACO代码解析Healthy Holsteins (holstein)


使喂给牛的饲料的种数最少。 给出牛所需的最低的维他命量,输出喂给牛需要哪些种类的饲料,且所需的饲料剂量最少。 维他命量以整数表示,每种饲料最多只能对牛使用一次,数据保证存在解。 [编辑]格式 PROGRAM NAME: holstein INPUT FORMAT:(file holstein.in) 第 1 行:一个整数 V(1<=V<=25),表示需要的维他命的种类数。 第 2 行:V 个整数(1<=每个数<=1000),表示牛每天需要的每种维他命的最小量。 第 3 行:一个整数 G(1<=G<=15),表示可用来喂牛的饲料的种数。 下面 G 行,第 n 行表示编号为 n 饲料包含的各种维他命的量的多少。 OUTPUT FORMAT:(file holstein.out) 输出文件只有一行,包括 牛必需的最小的饲料种数 P 后面有 P 个数,表示所选择的饲料编号(按从小到大排列) 。 如果有多个解,输出饲料序号最小的(即字典序最小) 。 [编辑]SAMPLE INPUT 4 100 200 300 400 3 50 50 50 50 200 300 200 300 900 150 389 399 [编辑]SAMPLE OUTPUT 213

#include<cstdio> int book[27],mark[17],stad[27],a[17][27],n,v,min=10000,min_mark[17],ans=0; void put_in(int x) { for(int i=1;i<=v;i++) book[i]+=a[x][i]; mark[x]=1; ans++; return; } void put_out(int x) { for(int i=1;i<=v;i++) book[i]-=a[x][i]; mark[x]=0; ans--; return; }

int pd() { for(int i=1;i<=v;i++) if(book[i]<stad[i]) return 0; return 1; } void copy_ans(int x) { min=x; for(int i=1;i<=n;i++) min_mark[i]=mark[i]; } void dfs(int step) { if(pd() && ans<min) { copy_ans(ans); return; } if(step==n+1) return; put_in(step+1); dfs(step+1); put_out(step+1); dfs(step+1); //该位置一 // //该位清零 //

} int main() { freopen("holstein.in","r",stdin); freopen("holstein.out","w",stdout); scanf("%d",&v); for(int i=1;i<=v;i++) scanf("%d",&stad[i]); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=v;j++) scanf("%d",&a[i][j]); put_in(1); dfs(1); put_out(1); dfs(1); printf("%d ",min); int sum=0;

// V 维生素数 // 维生素标准[] //N 饲料数

// a[i][j] 饲料 i 的第 j 种维生素数量

for(int i=1;i<=n;i++) if(min_mark[i]) { sum++; printf("%d",i); if(sum!=min) printf(" "); } printf("\n"); return 0; }


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com