动态规划专题分类视图
数轴动规题： 1
较复杂的数轴动规 4
线性动规 7
区域动规： 14
未知的动规： 20
数轴动规题：
题1.2001年普及组第4题--装箱问题
【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0<n≤30),每个物品有一个体积（正整数）。要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
【输入格式】输入文件box.in有若干行。第一行：一个整数，表示箱子容量V； 第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。
【输出格式】 输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余空间。 【输入样例】
24
6
8
3
12
7
9
7
【输出样例】
0
题2.1996年提高组第4题--砝码秤重 __数据加强版 【问题描述】设有n种砝码,第k种砝码有Ck个,每个重量均为Wk,求：用这些砝码能秤出的不同重量的个数，但不包括一个砝码也不用的情况。
【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数.
第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量.
【输出格式】输出文件weight.out中只有一行数据:Total=N。表示用这些砝码能秤出的不同重量数。
【输入样例】
2
2 2
2 3
【输出样例】
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的只有一行,该行只有一个整数,表示最小的质量差.
【样例输入】
5
5
8
13
27
14
【样例输出】
3
题4.补圣衣
【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...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...Ds4≤60)
【输出】输出一行,为修好四件衣服所要的最短时间。
【样例输入】
1 2 1 3
5
4 3
6
2 4 3
【样例输出】
20
【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。 假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需 要的时间是ti小时。但是由于老师们互相不商量，因此光光有可能不能完成老师的作业。当不能完成老师的作业时，光光就事后去向老师说明，然后被老师批评一顿了事。对于一件作业，只有2种情况：完成或者不完成（快要完成也算不完成）。如果没完成，受到批评是天经地义的。但是，不同的作业对于光光来说，批评的力度是不同的。第i件作业如果没完成，就要受到pi个单位的批评。多次这样之后，光光想要在长假前就知道他至少会受到多少个单位的批评。你能帮助他吗？
【输入】输入文件homework.in包含以下内容：第一行只有一个数字k,表示光光一共有的时间数;第二行只有一个数字n,表示作业数;接下来n行，每行两个数字，分别是ti和pi，两个数字之间用一个空格分开。
【输出】输出文件homework.out只包含一行，该行只有一个数字，代表了光光最少受到的批评。
【样例输入】
5
3
2 6
1 3
4 7
【样例输出】
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个数 Ti Gi Vi 表示各礼物的完美值、重量和体积
【输出】
输出共一个数，表示可能获得的最大完美值。
【输入输出样例】
输入(pack.in)：
6 5
4
10 2 2
20 3 2
40 4 3
30 3 3
输出(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≤300
80%到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
输出小卡卡和农夫所挤的牛奶量的最小差值。
Sample Input
6
7 9 2 6 4 2
Sample Output
0
题8.一般性的最少硬币组成问题 coinYB.
从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个公司能获得的盈
利情况如下：
最大盈利为6,方案为公司2使用2台,公司1使用1台.
题10.2001年浙江省队选拔---积木城堡castle.) 小XC发现垒城堡的时候,如果下面的积木比上面的积木大,那么城堡便不易倒。所以他在垒城堡的时候总是遵循这样的规则。小XC想把自己垒的城堡送给幼儿园里同学们，这样可以增加他的好感度。为了公平起见，他决定把送给每个同学一样高的城堡，这样可以避免同学们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。
为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。动态秤
任务：请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。
输入文件castle.in 第一行是一个整数N(N<=100)，表示一共有几座城堡。
以下N行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块，每块积木的棱长不超过100。
输出文件castle.out 一个整数，表示最后城堡的最大可能的高度。如果不到合适的方案，则输出0。
输入样例
2
2 1 –1
3 2 1 –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”。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议