《(完整版)2012福建省信息学奥林匹克CCF-NOIP夏令营第四天训练(附解题思路及参考程序).doc》由会员分享，可在线阅读，更多相关《(完整版)2012福建省信息学奥林匹克CCF-NOIP夏令营第四天训练(附解题思路及参考程序).doc（15页珍藏版）》请在金锄头文库上搜索。
1、(完整版)2012福建省信息学奥林匹克CCF NOIP夏令营第四天训练(附解题思路及参考程序)2012福建省信息学奥林匹克CCF NOIP夏令营第四天训练（附解题思路及参考程序）问题名称文件名输入文件输出文件时限分值最佳课题选择matmat.inmat。out1s100采药medicmedic。inmedic。out1s100装箱问题boxbox.inbox.out1s100乘法难题cardcard。incard.out1s100数字游戏gamegame。ingame.out2s100内存限制均为256M最佳课题选择（mat）【问题描述】Matrix67要在下个月交给老师n篇论文，论文的内容可
2、以从m个课题中选择。由于课题数有限,Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题i，若Matrix67计划一共写x篇论文，则完成该课题的论文总共需要花费AixBi个单位时间（系数Ai和指数Bi均为正整数）。给定与每一个课题相对应的Ai和Bi的值，请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文. 【输入文件】第一行有两个用空格隔开的正整数n和m，分别代表需要完成的论文数和可供选择的课题数。 以下m行每行有两个用空格隔开的正整数。其中，第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。 【输出
3、文件】输出完成n篇论文所需要耗费的最少时间。【样例输入】10 32 11 22 1【样例输出】19【样例说明】4篇论文选择课题一，5篇论文选择课题三，剩下一篇论文选择课题二,总耗时为241+1*12+251=8+1+10=19。可以证明，不存在更优的方案使耗时小于19。【数据规模与约定】对于30%的数据，n=10，m=5； 对于100%的数据，n=200，m=20，Ai=100，Bi=5。采药(medic）【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师.医师为了判断他的资质，给他出了一个难题.医师把他带到一个到处都是草药的山洞里对他说:
4、“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药.如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大.” 如果你是辰辰,你能完成这个任务吗？【输入文件】输入文件medic。in的第一行有两个整数T(1 = T = 1000）和M(1 = M = 100)，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数
5、，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】70 371 10069 11 2【样例输出】3【数据规模与约定】对于30%的数据，M = 10;对于全部的数据，M = 100。装箱问题（box）【问题描述】有一个箱子容量为v（正整数,ov20000），同时有n个物品（on30），每个物品有一个体积 （正整数)。要求从 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小.【输入文件】第一行，一个整数，表示箱子容量； 第二行，一个整数，表示有n个物品； 接下来n行，分别表示这n个物品的各自体积。【输出文件】一个整数,表示箱子剩余空间。【样例输入】2468312797【样例输出
6、】0【样例说明】3+9+12=24，可以正好将箱子装满【数据规模与约定】对于全部的数据, 0=n=30，0=v=20000乘法难题（card）【问题描述】 乘法难题是一种用一行的卡片来玩的单人游戏，每张卡片上有一个正整数。在游戏者从中拿出一卡片,并且得到一个分数，它等于被拿走的卡片上的数与这张卡片左右两张卡片上的整数的积。第一张与与最后一张卡片不能被拿出。在最后一次移动后，这行卡片中只剩下两张. 你的目标是怎样确定拿卡片的顺序,以使得总分数的值最小.例如，有一行的卡片，它上面的数字为10 1 50 20 5, 游戏者可以先取走1这张卡片，然后是20 和50，总分数为10*150 + 5020*
7、5 + 10*50*5 = 500+5000+2500 = 8000，如果他先拿50, 然接着20，最后取出1， 总分数为15020 + 1*20*5 + 1015 = 1000+100+50 = 1150。【输入文件】 输入文件的第一行包含卡片的总数N(3 = N = 100)，第二行包含N个范围在1到100之间的整数（两个整数之间有一个空格）。【输出文件】 输出文件包含一个整数，为最少的分数。【样例输入】610 1 50 50 20 5【样例输出】3650数字游戏(game)【问题描述】小W发明了一个游戏，他在黑板上写出了一行数字a1，a2，an，然后给你m个回合的机会,每回合你可以从中选
8、择一个数擦去它，接着剩下来的每个数字ai都要递减一个值bi如此重复m个回合,所有你擦去的数字之和就是你所得到的分数。 小W和他的好朋友小Y玩了这个游戏，可是他发现,对于每个给出的an和bn序列，小Y的得分总是比他高。小W很不服气，想让你帮他算算，对于每个an和bn序列,可以得到的最大得分是多少。这样他就知道有没有可能超过小Y的得分。【输入文件】 输入文件game.in的第1行，一个整数n(1n200),表示数字的个数。 第2行，一个整数m（1mn），表示回合数。 接下来一行有n个不超过10000的正整数，a1,a2，an，表示原始数字 最后一行有n个不超过500的正整数，b1，b2，bn，表示
9、每回合每个数字递减的值【输出文件】 一个整数，表示最大可能的得分.结果输出到文件game.out.【样例输入】3310 20 304 5 6【样例输出】47最佳课题选择题目大意：有n篇论文需要写，有m个课题可供选择，写x篇课题i的论文需要花费AixBi个单位时间，求完成n篇论文所需最小时间解题思路:Cij表示课题i写j篇论文所需时间Fij表示在前i种课题中写j篇论文所需的最小时间F1j=c1jFij=min(fi-1j-k+cik） k=0。j计算结果较大，注意使用int64参考程序：（C+）include #include include cstdlib#include cmath#incl
10、ude using namespace std；#define FOR（i,a,b） for(int i=a;i=b;i+)define MST(a，b） memset（a，b，sizeof(a）)define MAXN 205#define MAXM 25int n，m;int aMAXM,bMAXM;long long cMAXMMAXN;void init() scanf(dd，&n，m）； FOR（i，1，m） scanf（%d%d，ai，&bi）; ci0=0; FOR（j，1,n) cij=ai; FOR(k，1,bi）cij=cijj; long long fMAXMMAXN;v
11、oid work(） FOR(i，0,n)f1i=c1i; FOR（i,2,m） fi0=0； FOR（j，1，n) fij=fi1j; FOR(k,1,j)if (fi1j-k+cikfij）fij=fi-1j-k+cik； coutfmn；int main（） freopen（”mat。in”，r”,stdin）； freopen（mat。out”,w,stdout）; init(); work（）;(Pascal）var a,b，i,j，k，n,m:integer； c：array1.。20,1。.200 of int64; 预处理数组 f：array0。.200 of int64; b
12、egin assign（input，mat。in)；assign(output,mat.out)；reset(input)；rewrite（output）;readln(n,m); for k：=1 to m do begin readln（a,b）； for i:=1 to n do begin ck，i:=a; for j:=1 to b do ck,i:=ck,i*i； end； end； f0：=0； for i：=1 to n do fi：=100000000000000000; for k：=1 to m do for i：=n1 downto 0 do for j:=1 to n-i do if fi+ck,jfj then fj：=fjwi+ci； 注意初始状态和边界参考程序:var b：array1.。100000 of longint； i，c，d,m,t,j,o,k:longint;beginassi
