ACM题目与答案—C.pdf

零食零食 问题描述 小八同学最近爱上了吃零食，但是他又想追求健康的生活。每一包零食都有一个能量值，小八同学每次都一定要吃总能 量刚好为m的零食才肯罢休。而且小八同学又很懒，他希望通过吃数量最少的零食达到这个目的。所以他希望你能设 计一个程序帮他决定要吃哪些零食。 编程任务 给定每种零食所包含的能量和数目，给出所要吃的零食的最小数目。 数据输入 先输入一行包含2个整数m(m #include using namespace std; #define INF 1000000000 int dp20002,M; int knapsack(int num,int value) int i,t; for(i=M;i=value;i-) t = dpi-value+num; if(t0，表示该金矿为副矿，q是所属主矿的编号） 数据输出 输出只有一行，表示最多的金子数量。 输入文件示例输出文件示例输入文件示例输出文件示例 100 5400 80 100 0 40 500 1 20 300 1 20 100 0 50 200 0 #include #include using namespace std; int dp101; struct E int v; int p; int q; int f3;/主矿使用该数组记录其对应副矿的位置,f0默认值为0 a1001; int max(int x,int y)/取较大值函数 int b; b = x y? x: y; return b; int main() int N, M, i, j; while(scanf(“%d%d“, i = ai.v;j-) if(ai.f1 if(ai.f2 if(ai.f1 dpj=max(dpj,dpj-ai.v+ai.p);/只选主矿 printf(“%dn“,dpN);/输出工人数为N时的最大金子数 return 0; 卡片游戏卡片游戏 问题描述 小八同学最近开发了一款卡片收集的小游戏，在这个游戏中，小八同学布下了一个神奇的迷宫： 现在规定玩家只能向右或者向下走，向下走每次只能走一格，但是如果向右的话，则每次可以走一格或者走到列数是 当前所在列数数倍的格子，即，如果当前格子是（x， y） ，则下一步可以是（x+1，y） ， （x，y+1）或者（x，y*k） ，其中k1且为正整 数。 编程任务 计算玩家走出迷宫时所携带的最多的卡片数。 数据输入 第1行为两个正整数，用一个空格隔开：n m （其中n(1 using namespace std; int card211001; int path211001; int max(int a, int b); int main() int n = 0, m = 0; scanf(“%d%d“, int i = 1, j = 1; for (; i 0 ? temp : 0; int roleA = 2; while (roleA 0 ? temp_2 : 0); +roleA; for (j = 2; j 0 ? temp : 0); int k = 2; int roleA = j*k; while (roleA 0 ? temp_2 : 0); +k; roleA = j*k; int max(int a, int b) return a b ? a : b; for (i = 1; i 0),为每次boss对英雄的伤 害值。 ） 从第2行到第n+1行，第j行给出了编号为j-1的技能的基本数据，每行有2个非 负整数 ai bi （其中ai表示使用该技能花费的魔法值，bi表示使用该技能造成的伤害） 数据输出 输出只有一行，表示英雄杀死boss的时间，如果英雄被杀死，则输出“Gameover” 输入文件示例输出文件示例输入文件示例输出文件示例 4 2 254 10 5 20 10 30 28 76 70 输入文件示例输出文件示例输入文件示例输出文件示例 4 2 25 10 5 Game over 20 10 30 28 77 70 示例说明： 在两个示例中，除了最后一行数据，其余数据都一样。 其中boss打英雄每秒伤害为25,4秒之后英雄就会被boss打死。也就是说英雄最多有发动四次攻击的机会。 在4次攻击里，每一秒的顺序都是英雄先回复魔法值，然后英雄攻击boss，最后 boss攻击英雄。由于第一秒的回复值加上100会超出上限，所以这两点魔法值无法加入到魔法值总数中。这 才导致两个示例的结果不同 #include #include /using namespace std; int ai103,bi103; int xl103103;/xlij表示i次j蓝对boss的伤 害int max(int a,int b) if(ab) return a; return b; int main() int k,i,j,n,t,q,huihe,s,flag=0; /flag标记结束时的次数 scanf(“%d%d%d“, for(i=1;i100 ? 100: (j+t); /回蓝不超过100 if(j+aik=100) flag=i; break; if(flag) break; if(flag) printf(“%dn“,flag); else printf(“Gameover) return 0; 搬家 问题描述 搬家有多辛苦，相信你们早有耳闻。由于市区建设的需要，继小明之后，小八也加入了这个行列。现在的小八就陷入 了极度的纠结之中，看着家里的n件家具，小八开始发呆，因为n是一个小于2000的整数，实在是太多了，于是 小八决定随便搬2*k件家具就行了。但还是会很累，因为2*k也不小是一个不大于n的整数。 幸运的是小八有了上次帮小明搬东西的经验，发现每搬一次的疲劳度是左右手的物品的重量差的平方(这里补充一句， 小明每次搬两件东西，左手一件右手一件)。例如小八左手拿重量为3的物品，右手拿重量为6的物品，则他搬完这 次的疲劳度为(6-3)2=9 现在可怜的小八希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度)，请告诉他吧 编程任务 从给定的n件家具中，替小八挑选2*k件家具，并规划小八的搬运方案，使得小八最终的疲劳度最低。 数据输入 输入数据有两行,第一行有两个数n,k(2 #include using namespace std; #define INF 0x7fffffff /预定义32-bit int的最大值为正无穷大(也可以用0x3f3f3f3f) bool cmp(int x, int y)/sort函数默认从小到大,这里其实不需要比较函数 return x j * 2)/表明前i-1件物品足够配成j对,物品i没被选择,故i-1件与i件状态相同 dpij = dpi - 1j; else dpij = INF; /若i=2j,则最后两件物品必须配对,此时其状态与i-1不同,无穷大 if(dpij dpi - 2j - 1 + (ai - ai - 1