搜索
动态规划专题分类视图数轴动规题：...........................................1较复杂的数轴动规...................................4线性动规...................................................7区域动规：.............................................14未知的动规：.........................................20数轴动规题：题1.2001年普及组第4题--装箱问题【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0n≤30),每个物品有一个体积（正整数）。要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。【输入格式】输入文件box.in有若干行。第一行：一个整数，表示箱子容量V；第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。【输出格式】输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余空间。【输入样例】2468312797【输出样例】0题2.1996年提高组第4题--砝码秤重__数据加强版【问题描述】设有n种砝码,第k种砝码有Ck个,每个重量均为Wk,求：用这些砝码能秤出的不同重量的个数，但不包括一个砝码也不用的情况。【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数.第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量.【输出格式】输出文件weight.out中只有一行数据:Total=N。表示用这些砝码能秤出的不同重量数。【输入样例】22223【输出样例】Total=8【样例说明】重量2,3,4,5,6,7,8,10都能秤得【数据限制】对于100%的数据,砝码的种类n满足:1≤n≤100;对于30%的数据,砝码的总数量C满足:1≤C≤20;对于100%的数据,砝码的总数量C满足:1≤C≤100;对于所有的数据,砝码的总重量W满足:1≤W≤400000;题3.石子归并-szgb.pas【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差.【样例输入】558132714【样例输出】3题4.补圣衣【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20)第2行，为A1...As1共s1个数，表示第一件衣服上每个破损修好它所需的时间第3行，为B1...Bs2共s2个数，表示第二件衣服上每个破损修好它所需的时间第4行，为C1...Cs3共s3个数，表示第三件衣服上每个破损修好它所需的时间第5行，为D1...Ds4共s4个数，表示第四件衣服上每个破损修好它所需的时间(1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60)【输出】输出一行,为修好四件衣服所要的最短时间。【样例输入】12135436243【样例输出】20题5.光光的作业homework.pas/homework.exe【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需要的时间是ti小时。但是由于老师们互相不商量，因此光光有可能不能完成老师的作业。当不能完成老师的作业时，光光就事后去向老师说明，然后被老师批评一顿了事。对于一件作业，只有2种情况：完成或者不完成（快要完成也算不完成）。如果没完成，受到批评是天经地义的。但是，不同的作业对于光光来说，批评的力度是不同的。第i件作业如果没完成，就要受到pi个单位的批评。多次这样之后，光光想要在长假前就知道他至少会受到多少个单位的批评。你能帮助他吗？【输入】输入文件homework.in包含以下内容：第一行只有一个数字k,表示光光一共有的时间数;第二行只有一个数字n,表示作业数;接下来n行，每行两个数字，分别是ti和pi，两个数字之间用一个空格分开。【输出】输出文件homework.out只包含一行，该行只有一个数字，代表了光光最少受到的批评。【样例输入】53261347【样例输出】6【数据规模约定】100%的数据中,k≤100000,ti≤10000,pi≤10000;30%的数据中,n≤20;100%的数据中,n≤500;题7.打包[pack.pas/pack.c/pack.cpp]2006年OIBH新年赛【问题描述】你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下V体积物品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为G。现在你了解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划一下了。【输入】第一行：G和V表示最大重量和体积。第二行：N表示拿到N件礼物。第三到N+2行：每行3个数TiGiVi表示各礼物的完美值、重量和体积【输出】输出共一个数，表示可能获得的最大完美值。【输入输出样例】输入(pack.in)：6541022203240433033输出(pack.out)：50【数据范围】对于20%的数据N，V，G，Ti，Vi，Gi≤10对于50%的数据N，V，G，Ti，Vi，Gi≤100对于80%的数据N，V，G，Ti，Vi，Gi≤30080%到100%的数据是N，V，G，Ti，Vi，Gi≤380的离散随机数据。较复杂的数轴动规题6.挤牛奶-同济ACM第1132题Problem小卡卡终于帮农夫John找到了走丢的那一头奶牛，John为了感谢小卡卡，不仅告诉了他在Pascal山脉上可能存在Pascal圣地最大的宝藏，还说要请小卡卡喝牛奶。可是农夫John发现他家里所储藏的牛奶已经喝光了,所以要临时给奶牛挤奶。小卡卡实在是太好心了,说要帮农夫John一起挤牛奶。John答应了，他把他的n头奶牛中的n/2头（n是个偶数）分给小卡卡挤，他自己挤剩下的n/2头奶牛。但是每一头奶牛都有不同的产奶量,农夫John为了让小卡卡减轻负担,他希望他们两个所挤的牛奶的总量之差最小。小卡卡得知了每头奶牛的产奶情况之后很快就解决了这个问题。Input测试数据第一行一个整数n，n为偶数且小于100。表示有n头奶牛。第二行n个整数分别给出每头奶牛的产奶量（产奶量的总和不超过2000）。Output输出小卡卡和农夫所挤的牛奶量的最小差值。SampleInput6792642SampleOutput0题8.一般性的最少硬币组成问题coinYB.pas/coinYB.exe从n种币值为a[1..n]的硬币中,任选几个硬币组成价值为V的一堆货币,问最少需要几个硬币?其中每种硬币的数量没有限制。1=n=100,1=v=100000,1=a[i]=100000输入文件coinYB.in中有两行:第一行有两个数v和n;第二行有n个以空格分隔的数,表示n个币值.输出文件coinYB.out中只有一行,该行只有一个数,表示所需的最少硬币数,如果无论如何选取硬币,均不能得到币值v,则输出0.题9.多个公司间的机器分配问题已知第j个公司使用k台机器时,能得到的利润为a[j,k],问如何将m台机器在n个公司中分配,才能获得最大利润?要求输出能获得的最大利润及方案.将3台机器分配给2个公司能获得的盈利情况如下：公司号\机器数12312342145最大盈利为6,方案为公司2使用2台,公司1使用1台.题10.2001年浙江省队选拔---积木城堡castle.pas(castle.exe)小XC发现垒城堡的时候,如果下面的积木比上面的积木大,那么城堡便不易倒。所以他在垒城堡的时候总是遵循这样的规则。小XC想把自己垒的城堡送给幼儿园里同学们，这样可以增加他的好感度。为了公平起见，他决定把送给每个同学一样高的城堡，这样可以避免同学们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。任务：请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。输入文件castle.in第一行是一个整数N(N=100)，表示一共有几座城堡。以下N行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块，每块积木的棱长不超过100。输出文件castle.out一个整数，表示最后城堡的最大可能的高度。如果找不到合适的方案，则输出0。输入样例221–1321–1输出样例3题11.生物基元问题一个生物体的结构可以用“基元”的序列表示,一个“基元用一些英文字符串表示。对于一个基元集合P,可以将字符串S看作由n个基元P1,P2,…,Pn依次连接而成的。问题是给定一个字符串S和一个基元集合P,使S的前缀可由P中的基元组成。求这个前缀的最大长度。基元的长度最大为20,字符中的长度最大为500000.例如基元集合为{A,AB,BBC,CA},字符串为ABACABBCAACCB,则最大长度为10,其具体组成为题12.双塔2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr.F曾亲眼目睹了这次灾难。为了纪念“911”事件，Mr.F决定自己用水晶来搭建一座双塔。Mr.F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr.F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度,也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr.F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。输入的第一行为一个数N，表示水晶的数量。第二行为N个数，第i个数表示第i个水晶的高度。输出仅包含一行，如果能搭成一座双塔，则输出双塔的最大高度，否则输出一个字符串“Impossible”。样例输入：513452样例输出：7题41。过河river.pas/river.exe/river.c/river.cppABACABBCAA2214433311【问题描述】河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过