动态规划习题
动态规划专题分类视图
数轴动规题： (1)
较复杂的数轴动规 (4)
线性动规 (7)
区域动规： (14)
未知的动规： (20)
数轴动规题：
题1.2001年普及组第4题--装箱问题
【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 【输入格式】输入文件box.in有若干行。第一行：一个整数，表示箱子容量V； 第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。 【输出格式】输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余空间。 【输入样例】 24 6 8 3 12 7 9 7 【输出样例】 题2.1996年提高组第4题--砝码秤重__数据加强版 【问题描述】设有n种砝码,第k种砝码有C k个,每个重量均为W k,求：用这些砝码能秤出的不同重量 的个数，但不包括一个砝码也不用的情况。 【输入格式】输入文件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...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) 【输出】输出一行,为修好四件衣服所要的最短时间。 【样例输入】 1 2 1 3 5 4 3 6 2 4 3 【样例输出】 20 题5.光光的作业homework.pas/homework.exe 【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是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 题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个公司能获得的盈利情况如下： ,公司1使用1台. 题10.2001年浙江省队选拔---积木城堡castle.pas(castle.exe) 小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},字符串为AB A CA BBC AACCB,则最大长度为10,其具体组成为 AB A CA BBC AA 22 144333 11 题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”。样例输入： 5 1 3 4 5 2 样例输出： 7 题41。过河river.pas/ river.exe/ river.c/ river.cpp 【问题描述】河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L （其中L 是桥的长度）。坐标为0的点表示桥的起点，坐标为L 的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S 到T 之间的任意正整数（包括S,T ）。当青蛙跳到或跳过坐标为L 的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L ，青蛙跳跃的距离范围S,T ，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 【输入文件】输入文件river.in 的第一行有一个正整数L （1 <= L <= 109），表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数，其中1≤S ≤T ≤10,1 ≤M ≤100。第三行有M 个不同的正整数分别表示这M 个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 【输出文件】输出文件river.out 只包括一个整数，表示青蛙过河最少需要踩到的石子数。 【样例输入】 【样例输出】 【数据规模】 10 2 对于30%的数据，L <= 10000； 2 3 5 对于全部的数据，L <= 109。 2 3 5 6 7 线性动规 题22。1997年普及组第3题---街道路径条数 【问题描述】 设有一个N*M(l ≤N ≤50, l ≤M ≤50)的街道(如右图)： 规定行人从A(1,1)出发,在街道上只能向东或向北方向行 走。如图,从(1,1)点出发,至(3,3)点,共有6条不同的路径： (1,1)-(2,1)-(3,1)-(3,2)-(3,3)； (1,1)-(2,1)-(2,2)-(3,2)-(3,3)； (1,1)-(2,1)-(2,2)-(2,3)-(3,3)；(1,1)-(1,2)-(2,2)-(3,2)-(3,3)； (1,1)-(1,2)-(2,2)-(2,3)-(3,3)； (1,1)-(1,2)-(1,3)-(2,3)-(3,3)；若在N*M 的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通行,如图中用阴影线表示的部分。此矩形障碍区域可以用2对顶点坐标给出,如上图中的障碍区域以2对顶点坐标(2,2),(8,4)表示。此时,从A(1,1)出发至B(9,5),只有两条路径： 路径一：(1,1)-(2,1)-(3,1)-(4,1)-(5,1)-(6,1)-(7,1)-(8,1)-(9,1)-(9,2)-(9,3)-(9,4)-(9,5) 路径二：(1,1)-(1,2)-(1,3)-(1,4)-(1,5)-(2,5)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(8,5)-(9,5) 程序要求：任务一：给出N,M 后,求出所有从(1,1)出发到达(N,M)的路径的条数。 任务二：给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,Y1), (X2,Y2), 然后求出此种情况下所有从(1,1)出发到达(N,M)的路径的条数。 【输入格式】输入文件street.in 的第一行只有一个数字,1代表任务一,2代表任务二。 1)任务一：第二行有两个数字,表示N 和M 2)任务二：第二行有两个数字,表示N 和M ； 第三行有两个数字,表示矩形障碍的左下角坐标； 第四行有两个数字,表示矩形障碍的右上角坐标； 【输出格式】输出文件street.out 的只有一个数字,表示求得的路径条数。 东 【输入样例1】 1 3 3 【输出样例1】 6 【输入样例2】 2 9 5 2 2 8 4 【输出样例2】 2 题23。2002年普及组第4题--过河卒Array【问题描述】 如右图,A 点有一个过河卒,需要走到目标B 点。卒行走规则:可以 向下、或者向右。同时在棋盘上的某一点有一个对方的马(如上图的C 点),该马所在的点和所有跳跃一步可达的点称为马的控制点。例如右 图C点上的马可以控制9个点(图中的P1,P2,…,P8和C)。卒不能通过 对方马的控制点。棋盘用坐标表示,A 点坐标为(0,0)、B 点坐标为(n,m) (n,m为不超过20 的整数),同样马的位置坐标是需要给出的(约定点:C≠点A,同时点C≠点B)。现在要求你计算出卒从A 点到达 B 点的路径的条数。 【输入格式】输入文件p4.in只有一行数据,该行中有4个以空格分隔的数,表示B点的坐标和马的坐标【输出格式】输出文件p4.out只有一行数据,该行只有一个数,表示求得的路径条数。 【输入样例】 6 6 3 2 【输出样例】 17 题24。1997年普及组第1题---统计正方形和长方形个数 【问题描述】 设有一个n*m方格的棋盘(1≤m,n≤1000),求出该棋盘中包含多少个正方形、多少个长方形(不包括正方形)。例如：当n=2,m=3时, 正方形的个数有8个；长方形的个数有10个； 【输入格式】输入文件square.in只有一行数据,包含2个以逗号分隔的数,分别代表n和m 【输出格式】输出文件square.out只有一行数据,包含2个以逗号分隔的数,分别代表正方形的个数和长方形的个数。 【输入样例】 2,3 【输出样例】 8,10 题25。1997年提高组第3题-骑士游历 【问题描述】 设有一个n*m的棋盘(2≤n≤50,2≤m≤50) ,在棋盘上左下角(1,1)处有一个中国象棋马。马走的规则为：(1)马走日字；(2)马只能向右走。如图1所示。 任务1：当n,m输入之后,找出一条从左下角到右上角的路径。若不存在路径, 例如,如图2所示,输入：n=4,m=4,则输出路径：(1,1)-(2,3)-(4,4)(不唯一) 任务2：当n,m给出之后,同时给出马起点的位置和终点的位置,试找出从 起点到终点的所有路径的数目。如图3所示,给出马的起点坐标为(1,8),终 点坐标为(3,8),则有2条路径。 【输入格式】 从文件horse.in输入,第一行只有一个数字,1代表任务1,2代表任务2。 1)任务1：第2行有两个数,表示右上角坐标(n,m) 2)任务2：第2行有两个数,表示右上角坐标(n,m) 第3行有两个数,表示起点坐标(x1,y1) 第4行有两个数,表示终点坐标(x2,y2) 【输出格式】 输出至文件horse.out中。1)任务1：输出一条路径。2)任务2：输出一个数,表示路径数。【输入样例1】【输出样例1】 1 (1,1)-(2,3)-(4,4) 4 4 【输入样例2】【输出样例2】 2 2 10 10 1 8 3 8 题26。2000年提高组第4题--方格取数 【问题描述】 设有N*N的方格图(N<=30,我们将其中的某些方格中填入正整数, 而其他的方格中则放入数字0。如右图所示,表示样例数据的情况. 某人从图的左上角的A 点出发,可以向下行走,也可以向右走,直到到达右下角的B点。在走过的路上, 他可以取走方格中的数(取走后的 马 图1 马的4种走法 点A 方格中将变为数字0)。此人从A点到B 点共走两次,试找出2条这样 的路径,使得取得的数之和为最大。 【输入格式】输入文件4.in的第一行为一个整数N(表示N*N的方格图), 接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的0表示输入结束 【输出格式】输出文件4.out中中只有一行数据,该行只有一个数字,表示2条路径上取得的最大的和。【输入样例】【输出样例】 8 67 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 题27。NOIP2003年普及组第3题--栈(p2003_3.pas) 【问题背景】 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。 【问题描述】 宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n，栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）使用这两种操作,由一个操作数序列就可以得到一系列的输出序列。你的程序将对给定的n，计算并输出由操作数序列1，2，…，n经过操作可能得到的输出序列的总数。 【输入格式】输入文件STACK.in只含一个整数n（1≤n≤18） 【输出格式】输出文件STACK.out只有一行，即可能输出序列的总数目 【输入样例】【输出样例】 3 5 【思考】 如果1≤n≤3000，如何做？ 题28。花店橱窗布置问题(IOI99试题) 假设想以最美观的方式布置花店的橱窗,有F束花,每束花的 品种都不一样,同时,至少有同样数量的花瓶被按顺序摆成一行, 花瓶的位置是固定的,并按从左到右,从1到V顺序编号,V是花 瓶的数目,编号为1的花瓶在最左边,编号为V的花瓶在最右边 花束可以移动,并且每束花用1到F的整数唯一标志.标志花束的整数决定了花束在花瓶中排列的顺序,即如果i 题29。2007年宁波高中组第3题--宝石/ 1996年提高组第3题--挖地雷 【问题描述】 在一处原始森林中，发现了N个藏有宝石的山洞，这N个山洞以1至N编号。某些山洞间可能会有通道相连，山洞间的通道是单向的，编号较小的山洞可以通过通道走至编号较大的山洞，编号较大的山洞不可以通过通道走至编号较小的山洞。你可以选择任意一个山洞进入，选择一条通道，进入下一个较大编号的山洞，…，最后从某个山洞出来，并获得所有经过的山洞中的宝石。从外面只能进入一次，然后从一个山洞至另一个山洞，直至走出山洞。现在告诉你每个山洞中的宝石数，以及山洞之间的通道情况，求最多能取得多少宝石？ 【输入】输入文件gem.in有若干个行数据。 第一行有两个整数n和m，分别表示山洞数和通道数，两数间以一个空格分隔。 第二行有n个整数，第一个数表示第一个山洞的宝石数,第二个数表示第二个山洞的宝石数,…，第n个数表示第n个山洞的宝石数。这n个数间互相以一个空格分隔。 以下m行，每行描述两个山洞间有一条从编号较小山洞通向编号较大山洞的单向通道。每一行的两个整数a和b,可能表示山洞a至山洞b间的单向通道，也可能表示山洞b至山洞a间的单向通道。a和b间有一个空格分隔。 【输出】输出文件gem.out中只有一行，该行只有一个整数，表示最多能获得的宝石数。 【数据限制】 本题共有10组测试数据，每组10分，共100分， 对于所有的数据，获得的宝石总数不会超过2×109 30%的数据, 1≤n≤1000，0≤m≤10000 100%的数据, 1≤n≤20000，0≤m≤100000 【输入样例】【输出样例】 5 6 27 10 8 4 7 6 1 3 1 2 1 4 3 4 3 5 4 5 题30。1999提高组第1题-拦截导弹 【问题描述】 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）：1）计算这套系统最多能拦截多少导弹；2）如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 【输入格式】输入文件missile.in只有一行数据,包括若干以空格分隔的正整数,表示来袭的导弹的高度. 【输出格式】输出文件missile.out应包括二行数据。 第一行只有一个正整数,表示最多能拦截的导弹数; 第二行也只有一个正整数,表示要拦截所有导弹最少要配备的系统数。 【输入样例】 389 207 155 300 299 170 158 65 【输出样例】 6 2 题31。2004年提高组第3题-合唱队形 【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<... 【输入格式】输入文件chorus.in有2行数据。第一行是一个整数n(2<=n<=100)，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 【输出格式】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 【输入样例】 8 186 186 150 200 160 130 197 220 【输出样例】 4 【数据规模】 对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。 题32。渡河 Problem iRabbit的国家被一条河流(河流是直的)分成南北两岸，南北两岸各有N个城市。北岸的每一个城市有一个唯一的友好城市在南岸，且他们的友好城市彼此不同。为了城市关系的发展，每对城市之间都想要开通轮渡。由于河面上常常有雾。iRabbit决定禁止船只航线相交。以避免发生安全事故。iRabbit希望能在保证安全的情况下，尽可能多地开通航线。由于N非常大（1<=N<=2004），所以必须用程序解决。iRabbit因为备战竞赛，所以十分繁忙，没有时间来编写程序，所以交给手下的TCR 和sceoy解决。可是他们两个想了很久都没有想出答案，所以想请你来帮助解决。 Input 输入文件ferry.in的第1行有1个整数：N（1≤N≤2004）。接下来N行,每行两个数A,B。表示这一对友好城市与河源头的距离(不过100000)，其中A代表北岸城市、B代表南岸城市。 Output输出文件ferry.out中只有一个整数。表示可以开通轮渡的最大线路数。 Sample Input Sample Output 7 4 22 4 2 6 10 3 15 12 9 8 17 17 4 2 a[I] b[I] 题33。最长公共子序列：勇闯黄金十二宫……射手宫-同济ACM第1108题 Problem “已知艾尔里斯和弟弟艾尔里亚的基因基本相同，由于基因表达起来不方便，所以就用n个数字来表示。(因为至今共发现100000种基因，所以每个数字都<=100000)兄弟之间的基因个数是相同的，就是说他们都有n个数字。且对于每个人，这n个数字互不相同。现在要求兄弟之间基因的最长公共部分。可以不连续。” Input文件LCS.IN第1行，为n(1<=n<=100000) 下面2行，每行n个数字，表示了一个人的所有基因。 Output文件LCS.OUT一行，为他们两人基因的最长公共部分的长度。 Sample Input Sample Output 7 3 1 2 3 4 5 6 7 7 6 5 4 1 2 3 题38。管状矿藏duct.pas/duct.exe/duct.c/duct.cpp 【问题背景】A公司在南极大陆发现了一个稀有金属矿，该矿沿直线分布，共有n个点，每个点有一定量的矿藏。由于覆盖着冰块，不能从中间开采，只能从两头开采。由于该稀有金属的在地球上存量非常稀少，市场上价格越来越高，已知开采第一天的价格为1，第二天的价格为2，依次类推。A公司决定每天从两头选择一头开采出所有该点的矿藏。 【输入格式】输入文件duct.in包含以下内容：第一行:一个整数n，代表有n个矿点。第二行:n个整数，代表每个矿点的矿藏量。 【输出格式】输出文件duct.out包含一行，该行只有一个整数，代表开采出所有矿藏最多能得到的钱数。 【样例输入】【样例输出】 4 21 1 2 3 1 【数据规模】 n<=1000，每点矿藏数不超过109，最多能得到的钱数<1012。 区域动规： 题13. 2003年提高组第3题--加分二叉树 【问题描述】 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree 的前序遍历 【输入格式】文件binary.in 第1行：一个整数n(n＜30)为节点个数。 第2行：n个用空格隔开的整数,为每个节点的分数(分数＜100）。 【输出格式】文件binary.out 第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 3 1 2 4 5 题14。2000年普及组第3题--乘积最大 问题描述： 今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生 诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N 的数字串，要求选手使用K 个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1) 3*12=36 2) 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友XZ 设计一个程序，求得正确的答案。 输入共有两行： 第一行共有2个自然数N ，K （6≤N ≤40，1≤K ≤6） 第二行是一个长度为N 的数字串。 输出所求得的最大乘积（一个自然数）。 样例输入 4 2 1231 样例输出 62 题15。NOIP2003年普及组第2题--数字游戏（p2003_2.pas) 【问题描述】 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n 个),你要按顺序将其分为m 个部分,各部分内的数字相加, 相加所得的m 个结果对10取模后再相乘,最终得到一个数k 。游戏的要求是使你所得的k 最大或者最小。例如,对于下面这圈数字（n=4，m=2）： 当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为 ((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还 是正数,对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。 【输入】 输入文件GAME.in 第一行有两个整数，n （1≤n ≤50）和m （1≤m ≤9）。 以下n 行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。 【输出】输出文件GAME.out 有两行,各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。 【输入样例】 2 4 -1 3 -1 4 2 4 3 -1 2 【输出样例】 7 81 题16。NOIP2001年提高组第3题--统计单词个数(t2001_3.pas) 问题描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1 输入：输入数据放在文本文件input3.dat中，其格式如下：第一行有二个正整数(p，k),表示输入字串有p行;分为k个部分。接下来的p行，每行均有20个字符。再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)接下来的s行，每行均有一个单词。 输出：输出文件output3.dat中只有一行,该行只有一个整数,表示得到的最多单词个数。 样例输入： 1 3 thisisabookyouareaoh 4 is a ok sab 样例输出 7 题17。多边形的三角划分 N个顶点的凸多边形，各顶点权值已知，要求划分成N-2个三角形，使各三角形顶点权值乘积之和为最小 如右图当n=4，各顶点的权值Array 分别为10,5,7,6时，所求最小 值为10*5*6+5*6*7=510。 输入： 第一行：一个整数n 第二行：n个整数,依次表示各顶点的权值 题18。二叉树数 求由n个结点构成的不同的二叉树数. 样例输入: 3 样例输出: 5 题19。石子合并--NOI1995 stone.pas/stone.cpp/stone.c/stone.exe 有n堆石子围成一个圆圈。现在需要把它们合并成一堆石子。每次合并时，只能合并相邻的两堆石子，所耗力气为两堆石子重量之和，合并得到的新堆的重量为原两堆重量之和。问最少需要耗费多少力气？ 输入文件stone.in中：第一行一个整数n，第二行n个整数，表示顺序排列的每堆石子的重量。 输出文件stone.out中：只有一行，该行只有一个整数，表示合并这n堆石子最少需要耗费的力气。数据规模：1<=n<=200，合并n堆石子最少需要耗费的力气不超过2*109。 样例输入； 3 1 3 5 样例输出： 13 题20。1的最优操作序列 (请考虑使用动态规划和其它方法解决此题) 在黑板上写了N（n≤10000）个1，进行如下操作：每次擦去其中两个数a、b，并写上数a*b+1，如此下去直至最后一个数A。请你编程序求出A的最大值。 输入文件bestone.in中只有一个整数N； 输出文件bestone.out中也只有一个整数,表示得到的最大值 样例输入 5 样例输出 7 题21。NOI2001上海选拔---排序工作量之新任务 问题描述 假设我们将序列中第i件物品的参数定义为Ai，那么排序就是指将A1,…,An从小到大排序。若i 输入：输入文件newsort.in中只有一行，该行只有两个整数n和t (1≤n≤20，0≤t≤n*(n-1)/2 )。 输出：输出文件newsort.out中有二行，第一行只有一个数,表示n个参数都不同的物品组成的序列集合中,逆序数为t的序列个数；第二行是所求物品参数序列。假设n个物品的参数分别为1到n。 样例输入 4 3 样例输出 6 1 4 3 2 题39。能量项链energy.pas/ energy.exe/ energy.c/ energy.cpp 【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。 需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(4⊕1)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。 【输入文件】输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数,所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i ≤N），当i 【输出文件】输出文件energy.out只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。 【输入样例】【输出样例】 4 710 2 3 5 10 题40。金明的预算方案budget.pas/budget.exe/budget.c/budget.cpp Array【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自 己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说："你的房间需要购买哪些 物品，怎么布置，你说了算，只要不超过N元钱就行"。今天一早，金明就开始做预 算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，右表就是 一些主件与附件的例子： 如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。 【输入文件】输入文件budget.in 的第1行，为两个正整数，用一个空格隔开：N m（其中N（<32000） 表示总钱数，m（<60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的 物品的基本数据，每行有3个非负整数v p q（其中v表示该物品的价格（v<10000），p表示该物 品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示 该物品为附件，q是所属主件的编号） 【输出文件】输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总 和的最大值（<200000）。 【输入样例】【输出样例】 1000 5 2200 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 题51 关路灯 【问题描述】 某一村庄在一条路线上安装了n盏路灯，每盏灯的功率（单位时间的耗电量）有大有小。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为，先算一下左边路灯的总功率，再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，这样可以最省电。而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。 现在已知老张走的速度为1米/秒；每个路灯的位置（是一个整数，即距路线起点的距离，单位：米）；以及功率（W），老张关灯所用的时间很短而可以忽略不计。 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。 第1行是两个数字n和c 第2行至第n+1行，每行有两个整数。其中第k+1 表示第k盏灯离路线起点的距离，第二个整数表示第k 以上n+1行中，每行的两个整数之间都有一个空格分隔。 【输出】输出文件power.out 求得的最少耗电量。(单位：J，1J＝1W·秒)。 【数据限制】本题共有10组测试数据，每组10分，共 30%的数据, 1≤n≤20 100%的数据, 1≤n≤1000 100%的数据, 求得的最小耗电量不大于1×108 未知的动规： 题34。Tom的烦恼 Problem Tom是一个非常有创业精神的人,由于大学学的是汽车制造专业,所以毕业后他用有限的资金开了一家汽车零件加工厂专门为汽车制造商制造零件。由于资金有限他只能先购买一台加工机器。现在他却遇到了麻烦,多家汽车制造商需要他加工一些不同零件(由于厂家和零件不同,所以给的加工费也不同）,而且不同厂家对于不同零件的加工时间要求不同(有些加工时间要求甚至是冲突的,但开始和结束时间相同不算冲突）。Tom当然希望能把所有的零件都加工完,以得到更多的加工费,但当一些零件的加工时间要求有冲突时,在某个时间内他只能选择某种零件加工(因为他只有一台机器),为了赚得尽量多的加工费,Tom不知如何进行取舍。现在请你帮Tom设计一个程序,合理选择部分(或全部)零件进行加工,使得得到最大的加工费。 Input文件tom.in第一行是一个整数n(n<=30000)，表示共有n个零件须加工。接下来的n行中，每行有3个整数，分别表示每个零件加工的时间要求。第一个表示开始时间,第二个表示该零件加工的结束时间,第三个表示加工该零件可以得到的加工费。注：数据中的每个数值不会超过100000. Output文件tom.out中只有一个整数，表示Tom可以得到的最大加工费。 例1：机器负荷分配问题 某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x )=10x （单位：百件），其中x 为投入生产的机床数量，年完好率为a =0.7；在低负荷下生产的产量函数为h(y)=6y （单位：百件），其中y 为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。 例2：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表： 时期(k) 1 2 3 4 需要量(d k ) 2（单位） 3 2 4 假定不论在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x 个单位产品的成本费用为： 若 0＜x ≤6 ， 则生产总成本＝3十1·x 若 x ＝0 ， 则生产总成本＝0 又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？ 例3：设某企业在第一年初购买一台新设备，该设备在五年内的年运行收益、年运行费用及更换新设备的净费用如下表：（单位：万元） 年份(k) 役龄(t) 运行收益()k g t 运行费用()k r t 更新费用()k c t 第一年 0 22 6 18 第二年 0 1 23 21 6 8 19 22 [1]POJ动态规划题目列表 容易： 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵，求平衡）, 1936,1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029,2039, 2063, 2081, 2082,2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353,2355, 2356, 2385, 2392, 2424, 不易： 1019,1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707,1733(区间减法加并查集), 1737, 1837, 1850, 1920(加强版汉罗塔), 1934(全部最长公共子序列), 1937(计算几何), 1964(最大矩形面积，O(n)算法), 2138, 2151, 2161(烦，没写), 2178, 推荐： 1015, 1635, 1636(挺好的), 1671, 1682, 1692(优化), 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411 状态 DP 树 DP 构造最优解四边形不等式单调队列 1015 Jury Compromise 1029 False coin 1036 Gangsters 1037 A decorative fence 1038 Bugs Integrated, Inc. 1042 Gone Fishing 1050 To the Max 1062 昂贵的聘礼 1074 Parallel Expectations 1080 Human Gene Functions 1088 滑雪 1093 Formatting Text 1112 Team Them Up! 1141 Brackets Sequence 1143 Number Game 动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么 动态规划练习题 [题1] 多米诺骨牌（DOMINO） 问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。 现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。 输入格式： 文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。 输出格式： 只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。 [题2] Perform巡回演出 题目描述: Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表. 输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束. 输出: 对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0. 样例输入: 样例输出： 第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。 顺序对齐 源程序名ALIGN.??? (PAS,C,CPP) 可执行文件名ALIGN.EXE 输入文件名ALIGN.IN 输出文件名 ALIGN.OUT 考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是AADDEFGGHC 和ADCDEGH。 AAD_DEFGGHC ADCDE__GH_ 每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置(A,D,D,E,G,H)匹配，三段空格，所以得分2*6+(-1)*3=9，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。 请你写个程序找出最佳右对齐方案。 输入 输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。 输出 一行，为最佳对齐的得分。 样例 ALIGN.IN AADDEFGGHC ADCDEGH ALIGN.OUT 9 _______________________________________________________________________________ 任务安排 源程序名BATCH.??? (PAS,C,CPP) 可执行文件名BATCH.EXE 输入文件名BATCH.IN 输出文件名 BATCH.OUT N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是T i。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数F i。请确定一个分组方案，使得总费用最小。 动态规划 装箱问题（01背包）： 有一个箱子容量为VV（正整数，0≤V≤20000），同时有n个物品（0 完全背包的模板题面是这样的：设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以无限选取)，使其重量的和小于等于M，而价值的和为最大。 完全背包 [无限量]的采摘药输入： 70 3 71 100 69 1 1 2 输出：140 每个数组在满足条件，可以遍历多次 01背包 实现代码：采药-传送门 输入： 70 3 71 100 69 1 1 2 输出：3 每个数组遍历一遍 题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1-5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第jj件物品的价格为v_[j]，重要度为w_[j]，共选中了k件物品，编号依次为j_1,j_2,…,j_k，则所求的总和为： w_[j_k]v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]。 1、单调递增最长子序列 描述 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf，长度为4 输入 第一行一个整数0 2、最长公共子序列 描述 如题，需要写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0 3、括号匹配 时间限制：1000 ms | 内存限制：65535 KB 描述 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N，表示测试数据组数(N<=10) 每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符， S的长度不超过100 输出 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组 测试输出占一行 样例输入 4 [] ([])[] ((] ([)] 样例输出 3 2 u v a动态规划题列表 SANY GROUP system office room 【SANYUA16H-SANYHUASANYUA8Q8- 103 Stacking Boxes 108 Maximum Sum maximum 111 History Grading 116 Unidirectional TSP 147 Dollars 164 String Computer 166 Making Change 231 Testing the Catcher 348 Optimal Array Multiplication Sequence 357 Let Me Count The Ways 437 The Tower of Babylon 473 Raucous Rockers 481 What Goes Up 497 Strategic Defense Initiative 507 Jill Rides Again 531 Compromise 562 Dividing Coins 590 Always on the Run 607 Scheduling Lectures 620 Cellular Structure 624 CD 674 Coin Change 702 The Vindictive Coach 709 Formatting Text 711 Dividing up 714 Copying Books 787 Maximum Sub-sequence Product 825 Walking on the Safe Side 836 Largest Submatrix 882 The Mailbox Manufacturers Problem 907 Winterim Backpacking Trip 909 The BitPack Data Compression Problem 910 TV game 926 Walking Around Wisely 944 Happy Numbers 986 How Many? 988 Many paths, one destination 990 Diving For Gold 991 Safe Salutations 10003 Cutting Sticks 10029 Edit Step Ladders 动态规划题目及其代码By LYLtim 1、数塔问题(tower.pas) 设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。 【样例输入】tower.in 5 {数塔层数} 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 【样例输出】tower.out max=86 【参考程序】 uses math; var n,i,j:byte; a:array[1..10,1..10]of word; f:array[1..10,1..10]of word; begin assign(input,'tower.in');reset(input); assign(output,'tower.out');rewrite(output); readln(n); for i:=1 to n do begin for j:=1 to i do read(a[i,j]); readln; end; fillchar(f,sizeof(f),0); for i:=1 to n do f[n,i]:=a[n,i]; for i:=n-1 downto 1 do for j:=1 to i do f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j]; writeln('max=',f[1,1]); close(input);close(output); end. 2、拦截导弹(missile.pas) 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）， 动态规划习题 Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】 动态规划专题分类视图数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 对于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...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) 【输出】输出一行,为修好四件衣服所要的最短时间。 【样例输入】 1213 5 43 6 243 【样例输出】 20 题5.光光的作业homework.pas/homework.exe 【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需要的时间是ti小时。但是由于老师们互相不 动态规划 一·动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解 创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。 二·动态规划法基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段 阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=….n.表示。 1.状态 状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是可以直接或者是间接可以观测的。描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。用X(k)表示第k阶段的允许状态集合。 n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。 根据演变过程的具体情况，状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。 2．决策 当一个阶段的状态确定后，可以做出各种选择从而演变 到下一阶段的某个状态，这种选择手段称为决策 （decision），在最优控制问题中也称为控制（control）描述决策的变量称为决策变量（decision virable）。 变量允许取值的范围称为允许决策集合（set of 动态规划总结 1.POJ 1160 Post Office Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 17936 Accepted: 9655 Description There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates. Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum. You are to write a program which, given the positions of the villages and the number of post offices, computes the least 信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。 【目录】 1.动态规划的动机和基本思想 1.1.解决重复子问题 1.2.解决复杂贪心问题 2.动态规划状态的划分方法 2.1.一维状态划分 2.2.二维状态划分 2.3.树型状态划分 3.动态规划的辅助与优化方法 3.1.常见辅助方法 3.2.常见优化方法 4.近年来Noi动态规划题目分析 4.1 Noi2005瑰丽华尔兹 4.2 Noi2005聪聪与可可 4.3 Noi2006网络收费 4.4 Noi2006千年虫 附录参考书籍与相关材料 1.动态规划的动机和基本思想 首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。 1.1 解决重复子问题 对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑(log2n / k)。而考虑下面这个问题： USACO 1.4.3 Number Triangles http://122.139.62.222/problem.php?id=1417 【题目描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。 【输入格式】 第一个行包含R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。 【输出格式】 单独的一行包含那个可能得到的最大的和。 【样例输入】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 【样例输出】 30 显然，我们同样可以把大问题化成小问题来解决。如样例中最底层的6就可以从次底层 2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配资金，使总效益值最大？## 表8－47 解：设S1－A,B,C项目的总投资额，S2－B、C项目的总投资额 S3－C项目的投资额； X k－k项目的投资额； （X1－A项目的投资额，X2－B项目的投资额，X3－C项目的投资额）W k（S k,X k）－对K项目投资X k后的收益：W k（S k,X k）＝W k (X k) T k (S k,X k)－S k+1=S k-X k f k (S k)－当K至第3项目允许的投资额为S k时所能获得的最大收益。为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S4＝0，建立递归方程 f4 (S k)=0 f k (S k)=max{ W k (X k)+f k +1(S k+1)} k=3,2,1 X k∈D k(S k) 第一步，K=3 f4(S4)=0 f3 (S3)=max{W3 (X3)+f4 (S4)} X3∈D3(S3) S4=S3-X3 第二步： K=2 f2 (S2)=max{W2 (X2)+f3 (S3)} X2∈D2(S2) S3=S2-X2 W2 (X2)+f3 (S2-X2) 第三步： K=1 f1 (S1) =max {W1 (X1)+ f2 (S2)} X1∈D1(S1) S2= S1- X1 W1 (X1)+ f2 (S1- X1) S1=4 →S2=1 →S3=1 ↓↓↓ X1*=3 X2*=0 X3*=1 A投资3百万，B不投资C投资1百万。 动态规划 1.最佳队形（bestqueue; 时限:1s; 128MB） 【题目描述】 要参加复赛了，大家都在体育馆门口集合完毕，由于这次参赛的人数较多，上车前需要排一下队，所有人自愿排成两队（分别定义为A和B队列，人数大于1且两队人数随意），Ms. Zhou给每位同学一张纸，每人默默写下一个字母代表自己，比如：郑逸宁写Z，吴天舒写W等等。 A队： 字母：c m c B队： 字母：s n m n 最佳队形为： 1、每个人前后可以有任意个空位，也可以没有空位； 2、两队在添加空位后长度必须一样，上图可以有多种方案使得A、B两队长度一致， 例如： 3、根据每个人所写的字母，我们定义A队与B队的距离为相应位置上的字母的距离总 和； 4、两队相应位置的距离定义为： （1）两个非空位的距离定义为它们的所写字母ASCII码的差的绝对值； （2）空位与其他任意非空位之间的距离为已知的定值K； （3）空位与空位的距离为0。 5、最佳队形为：在A、B的所有可能队形中，必定存在两个等长的队A’、B’，使得A’ 与B’之间的距离达到最小，这个队形就是最佳队形。 请你写一个程序，求出最佳队形时，A队与B队的距离。 【输入数据】 输入文件第一行为队列A每个人所写字母组成的字符串A； 第二行为队列B每个人所写字母组成的字符串B。（约定：A、B均由小写字母组成且长度均不超过2000）。 第三行为一个整数K（1≤K≤100），表示空位与非空位的距离。 【输出数据】 输出文件仅一行包含一个整数，表示所求得最佳队形A、B之间的距离。 【样例】 bestqueue.in bestqueue.in cmc 10 snmn 2 2. 数学作业（homework; 时限:1s; 128MB） 【问题描述】 数学竞赛刚刚结束，据说题目很难，不过信息学里面的数学题也不容易哦，题目描述很简单：求：方程x1+2x2+…+nx n=m的所有非负整数解（x1,x2,…,x n）的个数。例如，方程：x1+2x2+3x3+4x4+5x5=5有7组解：（5,0,0,0,0）、（3,1,0 ,0,0）、…、（0,0,0,0,1）。 运用你的数学思维加上强大的信息学能力，试试解决它吧！ 【输入数据】 2个整数n，m 【输出数据】 方程非负整数解的个数ans，如果解超过10^9，只需输出ans mod 10^9。 动态规划入门练习题 1.石子合并 在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20). (1)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小; (2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大; 输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔. 输出数据: 从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示. 输入输出范例: 输入: 4 4 5 9 4 输出: －４５９－４ －８－５９ －１３－９ ２２４－５－９４ ４－１４－４ －４－１８ ２２ 最小代价子母树设有一排数，共ｎ个，例如：22 14 7 13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小. 输入、输出数据格式与“石子合并”相同。 输入样例： 4 12 5 16 4 输出样例： －１２－５１６４ １７－１６－４ －１７－２０ ３７ 2.背包问题 设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。 输入数据： 第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔； 第二行N个数,为Ｎ种物品重量；两个数用空格分隔； 第三行N个数,为N种物品价值; 两个数用空格分隔； 输出数据： 第一行总价值； 以下N行，每行两个数，分别为选取物品的编号及数量； 输入样例： 4 10 2 3 4 7 1 3 5 9 输出样例： 12 2 1 4 1 3.商店购物 某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。 编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU 因为: 1朵花加2个花瓶: 优惠价:10 ICU 2朵花正常价: 4 ICU 输入数据 用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。两个文件中都只用整数。 第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。 第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然，优惠价要低于该组合中商品正常价之总和。 输出数据 在输出文件OUTPUT．TXT中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）动态规划例题
POJ 动态规划题目列表
动态规划讲解大全(含例题及答案)
动态规划练习试题和解答
动态规划习题
动态规划题库
动态规划试题
动态规划典型例题
uva动态规划题列表
动态规划题目和代码
动态规划习题完整版
动态规划法求解生产与存储问题
动态规划题目
动态规划习题精讲
最新动态规划习题答案
动态规划试题
经典的动态规划入门练习题