acm题目与答案—c

《acm题目与答案—c》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、零食★问题描述小八同学最近爱上了吃零食，但是他又想追求健康的生活。每一包零食都有一个能量值，小八同学每次都一定要吃总能量刚好为m的零食才肯罢休。而且小八同学又很懒，他希望通过吃数量最少的零食达到这个目的。所以他希望你能设计一个程序帮他决定要吃哪些零食。★编程任务给定每种零食所包含的能量和数目，给出所要吃的零食的最小数目。★数据输入先输入一行包含2个整数m(m<=20000)、n，表示小八需要吃能量值和为m的零食，而零食一共有n种，下面输入n行，每行2个整数，第一个表示该种零食的能量值（能量值大于0），第二个表示该种零食的

2、总数。所有零食的总数量不会超过50。★数据输出输出一行包含一个整数表示小八最少需要吃的零食数量，若小八无法通过吃零食达到m的能量值，则输出“Fail”。输入文件示例输出文件示例102441210输入文件示例输出文件示例102Fail4173#include#includeusingnamespacestd;#defineINF1000000000intdp[20002],M;intknapsack(intnum,intvalue){inti,t;for(i=M;i>=value;i-

3、-){t=dp[i-value]+num;if(t

4、num*2<=num){tempnum=tempnum<<1;temp=temp<<1;}else{tempnum=num-tempnum;if(tempnum!=0){temp=tempnum*value;knapsack(tempnum,temp);}break;}}}if(dp[M]==INF)printf("Fail");elseprintf("%d",dp[M]);return0;}金矿问题★问题描述有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了M座金矿，国王知道这个消息后非常高兴，他希望能够

5、把这些金子都挖出来造福国民。后他找到了这个领域的专家小八，对每一座金矿进行勘测，勘测发现挖掘每个金矿所需的人数是固定的（一个也不需要多，一个也不能少），而且这些金矿也有主矿和副矿的区别，主矿可以直接进行挖掘，但是副矿必须在挖掘完其对应的主矿后才能进行挖掘，否则会有相当的风险。每个主矿可能有0个、1个或2个副矿，每个副矿都只对应1个主矿，且副矿不会再有副矿。了解完这些后，国王决定派N个矿工去挖金矿。（N个矿工不一定要全部用完）★编程任务给出金矿数量M及矿工数量N，以及每个金矿的具体情况。求最多能获得的金子数量。★数据输入第

6、1行为两个正整数，用一个空格隔开：NM（其中N(2<=N<=100),表示所有矿工数量，M(2<=M<=1000),为金矿的数量。）从第2行到第M+1行，第j行给出了编号为j-1的金矿的基本数据，每行有3个非负整数vpq（其中v表示挖掘该金矿所需的矿工数目，p表示该金矿的含金量，q表示该金矿是主矿还是副矿。如果q=0，表示该金矿是主矿，如果q>0，表示该金矿为副矿，q是所属主矿的编号）★数据输出输出只有一行，表示最多的金子数量。输入文件示例输出文件示例10054008010004050012030012010005020

7、00#include#includeusingnamespacestd;intdp[101];structE{intv;intp;intq;intf[3];//主矿使用该数组记录其对应副矿的位置,f[0]默认值为0}a[1001];intmax(intx,inty){//取较大值函数intb;b=x>y?x:y;returnb;}intmain(){intN,M,i,j;while(scanf("%d%d",&N,&M)!=EOF){//输入N、Mfor(i=1;i<=M;i++){s

8、canf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);//输入vpqif(a[i].q!=0){//若当前输入为副矿a[a[i].q].f[++a[a[i].q].f[0]]=i;//则改变其对应主矿的数组f，使f[1]、f[2]分别记录副矿一、二的位置}}for(i=1;i<=M;i++){