动态规划练习【题目一览】
总分
【问题描述】
学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。
我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间M（1<=M<=10000）（不要担心，你要到了训练营中才会有长时间的比赛）和“种类”的数目N（1<=N<=10000）。后面的每一行将包括两个整数来描述一个“种类”：
第一个整数说明解决这种题目能得的分数（1<=points<=10000），第二整数说明解决这种题目所需的时间（1<=minutes<=10000）。你的程序应该确定我们应该从每个“种类”中选多少道题目使得能在竞赛的时间中得到最大的分数。
来自任意的“种类”的题目数目可能任何非负数（0或更多）。
计算可能得到的最大分数。
【输入格式】
输入文件中的第1行：M，N--竞赛的时间和题目“种类”的数目。
第2～N+1行：两个整数：每个“种类”题目的分数和耗时。
【输出格式】
输出文件中仅一行，包括那个在给定的限制里可能得到的最大的分数。
【输入输出样例】
输入：
300 4
100 60
250 120
120 100
35 20
输出：
605
从第2个“种类”中选两题第4个“种类”中选三题。
邮票
【问题描述】
已知一个N枚邮票的面值集合（如，{1分，3分}）和一个上限K——表示信封上能够贴K张邮票。计算从1到M的最大连续可贴出的邮资。
例如，假设有1分和3分的邮票；你最多可以贴5张邮票。很容易贴出1到5分的邮资（用1分邮票贴就行了），接下来的邮资也不难：
6 = 3 + 3
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1
然而，使用5枚1分或者3分的邮票根本不可能贴出14分的邮资。因此，对于这两种邮票的集合和上限K=5，答案是M=13。
【输入格式】
输入文件中的第一行：两个整数K和N（1<=K<=200，1<=N<=50）。K是可用的邮票总数，N是邮票面值的数量。
第二行..文件末：N个整数，每行15个，列出所有的N个邮票的面值，面值不超过10000。
【输出格式】
输出文件中的第一行：一个整数，从1分开始连续的可用集合中不多于K张邮票贴出的邮资数。
【输入输出样例】
输入：
5 2
1 3
输出：
13
家的范围
【问题描述】
农民约翰在一片边长是N（2<=N<=250）英里的正方形牧场上放牧他的奶牛（因为一些原因，他的奶牛只在正方形的牧场上吃草）。遗憾的是，他的奶牛已经毁坏一些土地。（一些1平方英里的正方形）农民约翰需要统计那些可以放牧奶牛的正方形牧场（至少是2×2的，在这些较大的正方形中没有小于1×1的部分被分割毁坏）。
你的工作要在被供应的数据组里面统计所有不同的正方形放牧区域（>2×2）的个数。当然，放牧区域可能是重叠。
【输入格式】
输入文件中的第1行：N，牧区的边长。
第2到n+1行：N个没有空格分开的字符。
0表示“那一个区段被毁坏了”，1表示“准备好被吃”。
【输出格式】
输出那些存在的正方形的大小和个数，一种一行。
【输入输出样例】
输入：
6
101111
001111
111111
001111
101101
111001
输出：
2 10
3 4
4 1
游戏
【问题描述】
有如下一个双人游戏：N（2<=N<=100）个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。
编写一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。
【输入格式】
输入文件中的第一行：正整数N，表示序列中正整数的个数。
第二行至末尾：用空格分隔的N个正整数（大小为1～200）。
【输出格式】
输出文件中只有一行，用空格分隔的两个整数：依次为玩家一和玩家二最终的得分。
【输入输出样例】
输入：
6
4 7 2 9
5 2
输出：
18 11
商店购物
【问题描述】
在商店中，每一种商品都有一个价格（用整数表示）。例如，一朵花的价格是2 zorkmids(z)，而一个花瓶的价格是5z。为了吸引更多的顾客，商店举行了促销活动。
促销活动把一个或多个商品组合起来降价销售，例如：
三朵花的价格是5z而不是6z，两个花瓶和一朵花的价格是10z而不是12z。编写一个程序，计算顾客购买一定商品的花费，尽量利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。
对于上面的商品信息，购买三朵花和两个花瓶的最少花费是：以优惠价购买两个花瓶和一朵花（10z），以原价购买两朵花（4z）。
【输入格式】
输入文件中包括一些商店提供的优惠信息，接着是购物清单。
第一行：优惠商品的种类数s（0<=s<=99）。
第二行..第s+1行：每一行都用几个整数来表示一种优惠方式。第一个整数n（1<=n<=5），表示这种优惠方式由n种商品组成。后面n对整数c和k（1<=k<=5，1<=c<=999），表示k个编号为c的商品共同构成这种优惠，最后的整数p（1<=p<=9999）表示这种优惠的优惠价。优惠价总是比原价低。
第s+2行：这一行有一个整数b（0<=b<=5），表示需要购买b种不同的商品。
第s+3行..第s+b+2行：这b行中的每一行包括三个整数：c，k和p（1<=c<=999，1<=k<=5，1<=p<=999）。c表示唯一的商品编号，k表示需要购买的c商品的数量。p表示c商品的原价。最多购买5×5=25个商品。
【输出格式】
输出文件中只有一行，输出一个整数：购买这些物品的最低价格。
【输入输出样例】
输入：
2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5
输出：
14
“破锣摇滚”乐队
【问题描述】
你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N首歌的版权。你打算从中精选一些歌曲，发行M张CD。每一张CD最多可以容纳T分钟的音乐，一首歌不能分装在两张CD中。
不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：歌曲必须按照创作的时间顺序在CD盘上出现。选中的歌曲数目尽可能地多。
【输入格式】
输入文件中的第一行：三个整数：N，T，M（1<=N<=20，1<=M<=20，1<=T<=20）。
第二行：N个整数，分别表示每首歌的长度，按创作时间顺序排列。
【输出格式】
一个整数，表示可以装进M张CD盘的乐曲的最大数目。
【输入输出样例】
输入：
4 5 2
4 3 4 2
输出：
3
麦香牛块
【问题描述】
农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看”，奶牛们说，“如果你用只有一次能装3块、6块或10块的三种包装盒装麦香牛块，你就不可能满足想要一次只想买1、2、4、5、7、8、11、14或17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”
你的任务是帮助这些奶牛。给出包装盒的种类数N（1<=N<=10）和N个代表不同种类包装盒容纳麦香牛块个数的正整数i（1<=i<=256），输出顾客不能用上述包装盒（每种盒子数量无限）买到麦香牛块的最大块数。如果在限定范围内所有购买方案都能得到满足，则输出0。范围限制是所有不超过2000000000的正整数。
【输入格式】
输入文件中的第1行：包装盒的种类数N。
第2行到N+1行：每个种类包装盒容纳麦香牛块的个数。
【输出格式】
输出文件中只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或0（如果在限定范围内所有购买方案都能得到满足）。
【输入输出样例】
输入：
3
3
6
10
输出：
17
最长前缀
【问题描述】
在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。
如果一个集合 P 中的元素可以通过串联（允许重复；串联，相当于Pascal中的“+”运算符）组成一个序列S，那么我们认为序列S可以分解为P中的元素。并不是所有的元素都必须出现。举个例子，序列ABABACABAAB可以分解为下面集合中的元素：
{A，AB，BA，CA，BBC}
序列S的前面K个字符称作S中长度为K的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。
【输入格式】
输入文件中的开头包括1..200个元素（长度为1..10）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个“.”的行。集合中的元素没有重复。接着是大写字母序列S，长度为1..200000，用一行或者多行的字符串来表示，每行不超过76个字符。换行符并不是序列S的一部分。
【输出格式】
输出文件中只有一行，输出一个整数，表示S能够分解成P中元素的最长前缀的长度。
【输入输出样例】
输入：
A A
B BA CA BBC
.
ABABACABAABC
输出：
11
货币系统
【问题描述】
母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。[In their own rebellious way]，他们对货币的数值感到好奇。传统地，一个货币系统是由1，5，10，20或25，50和100的单位面值组成的。
母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。举例来说，使用一个货币系统{1，2，5，10，…}产生18单位面值的一些可能的方法是：18×1，9×2，8×2+2×1，3×5+2+1等等其它。
编写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会适合long long（C/C++）和Int64（Free Pascal）。
【输入格式】
货币系统中货币的种类数目是V（1<=V<=25）。
要构造的数量钱是N（1<=N<=10000）。
第1行：两个整数V和N。
第2..V+1行：可用的货币V个整数（每行一个，每行没有其它的数）。
【输出格式】
输出文件中单独的一行包含那个可能的构造的方案数。
【输入输出样例】
输入：
3 10
1 2 5
输出：
10
垃圾陷阱
【问题描述】
卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D（2<=D<=100）英尺。
卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t（0 【输入格式】 输入文件中的第一行为两个整数，D和G（1<=G<=100），G为被投入井的垃圾的数量。 第二到第G+1行每行包括三个整数： ·T（0 ·F（1<=F<=30），表示该垃圾能维持卡门生命的时间； ·H（1<=H<=25），该垃圾能垫高的高度。 【输出格式】 如果卡门可以爬出陷阱，输出一个整表示最早什么时候可以爬出。否则输出卡门最长可以存活多长时间。 【输入输出样例】 输入： 20 4 5 4 9 9 3 2 12 6 10 13 1 1 输出： 13 样例说明： ·卡门堆放她收到的第一个垃圾：height=9； ·卡门吃掉她收到的第二个垃圾，使她的生命从10小时延伸到13小时； ·卡门堆放第三个垃圾，height=19； ·卡门堆放第四个垃圾，height=20。 神秘的咒语 【问题描述】 身为拜月教的高级间谍，你的任务总是逼迫你出生入死。比如这一次，拜月教主就派你跟踪赵灵儿一行，潜入试炼窟底。 据说试炼窟底藏着五行法术的最高法术：风神，雷神，雪妖，火神，山神的咒语。为了习得这些法术，要付出艰辛的努力，但是回报同样十分丰厚。 拜月希望你告诉他咒语的长度为多少。（你：“请问您想知道咒语的具体内容吗？”拜月：“想，但是vijos不支持special judge。”原来大人物也有大人物的悲哀…） 于是你偷偷躲在一边，想乘机看看咒语究竟是什么。突然，天空（？？试炼窟底看的到天空？？）出现了两条非常长的数字串，你抓狂了。究竟哪个才是真正的咒语呢？你突然想到，这两个都不是咒语（不妨称之为伪咒语），而真正的咒语却与他们有着密切的联系。于是你打开拜月亲手给你写的纸条：“The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length” “该死的拜月，居然还会E文！”你咒骂着，但为了一家老小的生命，又不得不卖命地算着咒语的长度。 【输入格式】 输入文件中的第一行为一个数N，代表有N组测试数据。 对于每组测试数据，描述了两条数字串，首先一个数字为一条伪咒语的长度M，接下来M个数描述了伪咒语的内容。 【输出格式】 输出文件中共N行，每行一个数字，描叙了对应咒语的长度。 【输入输出样例】 输入： 1 5 1 4 2 5 -12 4 -12 1 2 4 输出： 2 【数据范围】 对于100%的数据，有1<=N<=5，1<=M<=500，Ai，Bi在长整型范围内。 天堂的馈赠 【问题背景】 小杉找到了做棉花糖的最优方案，想去摘云朵，可是摔死了…… 他来到了天堂。 天堂当然是很大的，也是很缭乱的。 小杉看到一块路标，写着“天堂的馈赠”。 【问题描述】 考虑到小杉刚死没多久，为了安抚他受创的心灵和思恋的感情， 天堂派出一个天使给小杉送礼，但IQ不够高的小杉可不能够拿到好礼物。 馈赠在天堂门口进行。天使站在云端，往下扔礼物。 天堂之门的宽度为W格（按1..W编号），高度为0格，云端的高度为H格，小杉只能站在格子里。 开始时（第0秒），小杉站在天堂之门的第P格。 馈赠开始后，天使会在某些时刻从云端的某格扔礼物下来，礼物下落的速度（格/秒）是不一样的。 小杉左右移动去接礼物（每秒可以移动1格或不移动）。 礼物之间的价值当然是不一样的，小杉事先知道了每个礼物的价值。 当礼物在某一秒末恰好到达小杉所在的格子中，小杉就接到了这个礼物。 小杉想知道，他最多可以拿到价值为多少的礼物。 而且，由于礼物下落的速度有些可以很……，小杉还想知道是不是有些礼物他怎么样也拿不到。【输入格式】 输入文件中的第一行有四个数W，P，H，N（1<=P<=W<=500），（1<=H<=500），（0<=N<=3000）。 接下来N行，每行四个数t，r，v，s（0<=t<=1500），（1<=r<=W），（1<=v<=H），（|s|<=1e5）。 表示天使在t时刻，云端的第r格，以v格/秒的速度扔下价值s的礼物。 输入均为正整数。 【输出格式】 输出文件中有两行。第一行仅有一个整数，表示小杉最多能拿到价值多少的礼物。 第二行也仅有一个整数，表示小杉不可能拿到的礼物总价值多少。 【输入输出样例】 输入： 1 1 1 1 1 1 1 1 输出： 1 注释：注意：当礼物在某一秒末恰好到达小杉所在的格子中，小杉才能接到这个礼物。 【数据范围】 10%的数据W<=100，H<=100，N<=200。 上帝的爱好 【问题背景】 拿了一些礼物，小杉想走进天堂，可却被拦了下来。 因为上帝很喜欢词这个文体，他要求小杉必须写几首词来应对。 写的词越多，能带进天堂的刚才拿的礼物就越多。 【问题描述】 我们知道，词都是按照词牌来填的，上帝为了考验小杉，只给了他四种词牌，但只要压韵就算符合词牌。 小杉已经想好了N个意境优美的句子，每个句子都有一个韵脚。 符合要求的词的句式应当有如下四种“XXYY”，“XYXY”，“XYYX”，“XXXX”，其中X或Y表示韵脚。 现在小杉想知道，从他想的N个句子之中，最多能按顺序挑选出几首符合条件的词。 并且词的句子间不能交错，比如你选了1 4 6 8做为一首诗，那么7你就不能再选了。 【输入格式】 输入文件中的第一行有一个数N（N<=4000）。 第二行有N个不超过10000的正整数，第i个整数表示第i个句子的韵脚，整数相同表示韵脚相同。 【输出格式】 输出文件中仅一行一个数字，表示小杉最多能挑出几首词来。 【输入输出样例】 输入： 12 1 2 4 2 3 1 2 2 1 1 2 2 输出： 2 注释：样例最多可以挑出两首词，一种方案如下：1 2 4 6/9 10 11 12。 【数据范围】 30%的数据N<=100。 苹果旅游 【问题背景】 xiaoT发现山谷相当的大，准确地说应该是相当的长，xiaoT想到山谷的那头去看看，但是靠xiaoT 走路的速度，到那边要n年。还好xiaoT可以买一些苹果（？？苹果买苹果？？自相残杀or大义灭亲），它把这些苹果当成动力，根据火箭发射的原理（晕，这个苹果知道得真多），如果xiaoT把苹果向后扔，xiaoT就会向前进（Q：xiaoT能把苹果扔多远？A：xiaoT拥有超强的臂力。Q：xiaoT怎么会有手呢？A：…）。 【问题描述】 苹果有两种，一种青苹果，一种红苹果。 已知到山谷的长度为k，用一些（同一种类）苹果可以通过的路程为1。 苹果的价格是不一样的，红苹果的价格是红苹果个数的四次方。 青苹果的价格就是青苹果个数。 【输入格式】 输入文件中的第一行有一个正整数n，表示xiaoT走路到那边需要的时间。 第二行有一个正整数k，表示山谷的长度。 接下来k行，每行两个正整数，分别表示通过该段： ·如果使用红苹果，则需要的数量为a； ·如果使用青苹果，则需要的数量为b。 【输出格式】 输出文件中只有一个数，即买苹果的最少的花费。 【输入输出样例】 输入： 2296 3 3 1000 2 5000 4 8000 输出： 2296 样例解释：第1段用青苹果，第2、3段用红苹果，花费是1000+(2+4)4。 【数据范围】 对于30%的数据，k<=10； 对于50%的数据，k<=25； 对于100%的数据，k<=50； 对于100%的数据，每段路消耗的红苹果的数量<=10； 对于100%的数据，每段路消耗的青苹果的数量<=107。 文科生的悲哀 【问题背景】 化学不及格的Matrix67无奈选择了文科。他必须硬着头皮艰难地进行着文科的学习。 【问题描述】 这学期的政治、历史和地理课本各有n章。每一科的教学必须按章节从前往后依次进行。若干章政治、若干章历史和若干章的地理内容可以合成一个教学阶段。年级计划将整个学期的内容分成若干个阶段进行教学。为了保证各科教学进度相同，年级规定每一个阶段包含的各科的章节数必须相同。一个阶段包含的章节越多，这个阶段所需要的课时也就越多。经过研究，假如某个阶段包含政史地各k章，则政治学习需要花费3^k天的课时，历史学习需要花费5^k天的课时，地理学习需要花费2^k天的课时，最后还需要4天的综合训练。一个阶段所花费的总时间是以上四项时间的和。 为了便于安排时间，学校希望每个阶段恰好需要若干周来完成。因此，划分出的每一个阶段所需要的天数都必须是7的整数倍（高三是没有星期六和星期天的）。 那么，这学期的课程最多可以划分成多少个阶段呢？你会想到，要想划分的阶段数最多，一个阶段完成一章的任务就行了（因为3^1+5^1+2^1+4=14是7的整数倍）。但问题没有这么简单。每个课本都可能有一些独立性较强的连续章节，它们具有很强的连续性，必须在一个阶段中完成。如果你已知所有不能划分在两个或两个以上的阶段中的连续章节，你还能计算出最多能安排多少个阶段吗？ 【输入格式】 输入文件中的第一行有两个用空格隔开的正整数n和m，分别表示各科课本的章节数和不可分割的连续章节的个数。 第二行到第m+1行，每行告诉了一个信息，该信息说明了哪一个课本的第几章到第几章必须一次性完成。同一科目给定的章节有可能重复或有重叠。 每一行信息分为两个部分。第一部分是“Politics:”、“History:”、“Geography:”三个字符串中的一个；第二部分是用“-”连接的两个数字x，y（1<=x 【输出格式】 一个正整数，表示按照学校和年级的种种要求（见下）最多可以安排的阶段个数。 如果没有符合条件的安排方案，请输出-1。 注意：以下三个要求需要同时考虑。 1．每一个阶段包含的各科章数相同； 2．按时间函数计算出的各阶段所需天数必须是7的倍数； 3．给出的任一个连续章节都不能被分割开来。 【输入输出样例】 输入： 8 3 Politics:1-2 History:5-6 Politics:1-4 动态规划练习 输出： 3 样例说明： 最多可以安排三个阶段，具体方案如下： 第一阶段完成各科第1-6章的课程 第二阶段完成各科第7章的课程 第三阶段完成各科第8章的课程 Sample Input #2: 4 2 Geography:1-3 History:2-4 Sample Output #2: -1 【数据范围】 对于30%的数据，n，m<=10； 对于50%的数据，n，m<=1000； 对于100%的数据，n，m<=100000。 【问题描述】 OIBH运来一批装备（鼠标和键盘）。DaoThree要把这些装备分配给moderator们（每人一个鼠标，一个键盘）。可是问题来了…… 这些装备的型号不相同，把一个m型的键盘和一个n型的鼠标分配给一个moderator得到的不满意值为(m-n)^2（每个moderator当然希望自己得到的装备是同一型号的）。 你的任务就是帮帮DaoThree把a个键盘和b个鼠标分配给n个moderator。使他们的不满意值之和最小。 【输入格式】 输入文件中的第一行：三个正整数n，a，b（1<=n<=a，b<=80）。 第二行：a个数表示每个键盘的型号。 第三行：b个数表示每个鼠标的型号。 0<=型号值<=10000。 【输出格式】 输出文件中仅一个数，即最小不满意值。 【输入输出样例】 输入1： 2 3 3 9 10 20 0 10 11 输出1： 2 输入2： 3 4 4 3 9 7 4 4 2 5 5 输出2： 5 【数据范围】 对于30%的数据n<=10，a，b<=30； 对于100%的数据n<=75，a，b<=80。 【问题描述】 一个被分为n×m个格子的糖果盒，第i行第j列位置的格子里面有a[i][j]颗糖。本来tenshi打算送这盒糖果给某PPMM的，但是就在要送出糖果盒的前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。tenshi必须尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且tenshi希望保留在新糖果盒内的糖的总数尽量多。 任务：请帮tenshi设计一个程序计算一下新糖果盒最多能够保留多少糖果。 【输入格式】 输入文件中的第一行有两个整数n，m（1<=n，m<=300）。 第i+1行的第j个数表示a[i][j]（0<=a[i][j]<=255），如果这个数为0，则表示这个位置的格子被洗劫过。 【输出格式】 输出文件中为最大糖果数。 【输入输出样例】 输入： 3 4 1 2 3 4 5 0 6 3 10 3 4 0 输出： 17 注意：10 3 4这个矩形的糖果数最大。 能量项链 【问题描述】 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m×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。 【输入格式】 输入文件中的第一行是一个正整数N（4<=N<=100），表示项链上珠子的个数。 第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1<=i<=N），当i 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 【输出格式】 输出文件中只有一行，是一个正整数E（E<=2.1*109），为一个最优聚合顺序所释放的总能量。 【输入输出样例】 输入： 4 2 3 5 10 输出： 710 例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 动态规划讲解大全 动态规划(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. 样例输入: 样例输出： 2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配 资金，使总效益值最大？## 表8－47 解：设S－A,B,C项目的总投资额，S－B、C项目的总投资额21S－C 项目的投资额；3X－k项目的投资额；k（X－A项目的投资额，X －B项目的投资额，X－C项目的投资额）312W（S,X）－对K项目投资X后的收益：W（S,X）＝W (X) kkkkkkkkk T (S,X)－S=S-X k k+1kkkk f (S)－当K至第3项目允许的投资额为S时所能获得的最大收益。kkk为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S＝0，建立递归方程4f(S)=0 k4 f (S)=max{ W (X)+f(S)} k=3,2,1 k+1kk +1kkk X∈D(S) kkk第一步，K=3 f(S)=0 44 f (S)=max{W (X)+f (S)} 434333X∈D(S) 333S=S-X3 34 第二步：)} f (S (X (S)=max{W)+f K=2 322322) X ∈D(S 222-X =S S232 W (X)+f (S-X) 22322 第三步：)} (S (X) =max f (S {W)+ f K=1 211121) D X∈(S111- X S= S 1 21 ) (X- X)+ f (SW1 12 11 S=4 →S=1 →S=1 312↓↓ ↓ X*=3 X*=0 X*=1 312百万。1投资C 不投资B 百万，3投资A． 总收益164百万元。 3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。每个营业区至少设一家，所获利润如表。问设立的6家销售店数应如何分配，可使总利润最大？ 第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（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），输入称为输入状态，输出称为输出状态。 动态规划 装箱问题（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 动态规划习题 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.石子合并 在一个圆形操场的四周摆放着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中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品） 水题6 Barn Repair(Section 1.3) 修理牛棚 译by tim green 在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。好在许多牛正在度假，所以牛棚没有住满。剩下的牛一个紧挨着另一个被排成一行来过夜。有些牛棚里有牛，有些没有。所有的牛棚有相同的宽度。自门遗失以后,农民约翰很快在牛棚之前竖立起新的木板。他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。农民约翰想将他购买的木板总长度减到最少。给出M(1<= M<=50),可能买到的木板最大的数目;S(1<= S<=200),牛棚的总数;C(1 <= C <=S) 牛棚里牛的数目,和牛所在的牛棚的编号 stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。输出所需木板的最小总长度作为的答案。 PROGRAM NAME: barn1 INPUT FORMAT SAMPLE INPUT (file barn1.in) 4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 OUTPUT FORMAT 单独的一行包含一个整数表示所需木板的最小总长度。SAMPLE OUTPUT (file barn1.out) 25 [ 一种最优的安排是用板拦住牛棚3-8,14-21,25-31,40-43.] Number Triangles(Section 1.5) 数字金字塔 译by tim green 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的样例中,从7 到3 到8 到7 到5 的路径产生了最大和:30 PROGRAM NAME: numtri INPUT FORMAT 第一个行包含R(1<= R<=1000) ,表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 所有的被供应的整数是非负的且不大于100。 SAMPLE INPUT (file numtri.in) 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 OUTPUT FORMAT 单独的一行包含那个可能得到的最大的和。 SAMPLE OUTPUT (file numtri.out) 30 一、关键子工程（project.c/cpp/pas） 在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、……、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设： （1）根据预算，每一个子工程都有一个完成时间。 （2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。 （3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。 （4）整个工程的完成是指：所有子工程的完成。 其中，表格中第I+1行J+2列的值如为0表示“子工程I”可以在“子工程J”没完成前施工，为1表示“子工程I”必须在“子工程J”完成后才能施工。上述工程最快完成时间为14天，其中子工程1、3、4、5为关键子工程。 又例如，有五个子工程的工程规划表： 上述的子工程划分不合理，因为无法安排子工程1，3，4的施工。 输入数据： 第1行为N，N是子工程的总个数，N≤200。 第2行为N个正整数，分别代表子工程1、2、……、N的完成时间。 第3行到N+2行，每行有N-1个0或1。其中的第I+2行的这些0，1，分别表示“子工程I”与子工程1、2、…、I-1、I+1、…N的依赖关系，（I=1、2、……、N）。每行数据之间均用一个空格分开。 输出数据： 动态规划复习： 《便宜的旅行》分析： 这个问题很明显是一个动态规划的标准问题。 考虑某一天晚上车队到达了终点，上一次的花销必然是只与早上车队所在的位置有关的。这样，由于要求从起点到终点最优的方案，所以从起点到达早上所出发时旅馆的方案也应该是最优的。以此类推，我们可以得出我们应该求出从起点到各个旅馆的最优方案。这样，如果我们设从起点到旅馆s i∈S (1≤ i≤ n)的最优方案的价值为f(s i)，就可以得到如下的动态规划方程： F(s[i])=min{f(s[j])}+value[i]; 0<=s[i]-s[j]<=800 这里value(s i)为s i的价值。 《蛙人》 设F(i,j) 是携带i升氧气，j升氮气的最小重量 F(i+a k,j+t k)=min{f(i,j)+W k} 李曙华同学程序 for i:=0 to 21 do for j:=0 to 79 do a[i,j]:=10000000; a[0,0]:=0; for i:=1 to n do begin readln(b[i,1],b[i,2],b[i,3]); for j:=21-b[i,1] downto 0 do for k:=79-b[i,2] downto 0 do begin if a[j,k]>a[j,k+1] then a[j,k]:=a[j,k+1]; if a[j,k]>a[j+1,k] then a[j,k]:=a[j+1,k]; if a[j+b[i,1],k+b[i,2]]>a[j,k]+b[i,3] then a[j+b[i,1],k+b[i,2]]:=a[j,k]+b[i,3]; end; end; writeln(a[x,y]); close(input);close(output); end. 动态规划专题分类视图 数轴动规题： (1) 较复杂的数轴动规 (4) 线性动规 (7) 区域动规： (14) 未知的动规： (20) 数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 的个数，但不包括一个砝码也不用的情况。 【输入格式】输入文件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、三角数塔问题 设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走 或向右走，如图所示： 要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。 【代码】 // // 例题1 三角数字塔问题// // #include scanf("%d",&a[i][j]); for(i=1; i<=n; i++) for(j=1; j<=i; j++) d[i][j]=-1;//初始化指标数组 printf("递推方法：1\n记忆化搜索方法：2\n"); int select; scanf("%d",&select); if(select==1) { fnRecursive(i,j);//调用递推方法 printf("\n%d\n",d[1][1]); } if(select==2) { printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法} else printf("输入错误！"); return 0; } voidfnRecursive(inti,int j) //递推方法实现过程 { for(j=1; j<=n; j++) d[n][j]=a[n][j]; for(i=n-1; i>=1; i--) for(j=1; j<=i; j++) d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]); } intfnMemorySearch(inti,int j) //记忆化搜索实现过程 { if(d[i][j]>=0) return d[i][j]; if(i==n) return(d[i][j]=a[i][j]); if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1)) return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j))); else return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1))); } 2、硬币问题 信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的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就可以从次底层 动态规划部分常见题目 作者: 发表于2011-06-10 14:20:49【大中小】浏览:230次评论:0条 求两个字符串的最长公共子序列 0-1背包问题 骑士游历 设有一个n*m的棋盘(2<=n<=50,2<=m<=50),在棋盘上任一点有一个中国象棋马,马走的规则为:1.马走日字 2.马只能向右走. 任务1:当N,M 输入之后,找出一条从左下角到右上角的路径. 例如:输入 N=4,M=4 输出:路径的格式:(1,1)->(2,3)->(4,4) 若不存在路径,则输出"no" 任务2:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目. 例如:(N=10,M=10),(1,5)(起点),(3,5)(终点) 输出:2(即由(1,5)到(3,5)共有2条路径) 输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标) 输出格式:路径数目(若不存在从起点到终点的路径,输出0) 数字三角形 （图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路 径，使该路径所经过的数字的总和最大。 ●每一步可沿左斜线向下或右斜线向下走； ●1＜三角形行数≤100； ●三角形中的数字为整数0，1，…99； 输入数据： 由INPUT.TXT文件中首先读到的是三角形的行数。 在例子中INPUT.TXT表示如下： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出数据： 把最大总和（整数）写入OUTPUT.TXT文件。上例为： 30 ７ ３８ ８１０ ２７４４ ４５２６５ （图３.１－１） 添加号 有一个由数字1，2，... ，9组成的数字串（长度不超过200），问如何将M(M<=20)个加号("+")插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。 注意： 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。 M保证小于数字串的长度。 例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。动态规划例题
动态规划讲解大全(含例题及答案)
动态规划练习试题和解答
动态规划习题答案
动态规划习题
动态规划试题
动态规划典型例题
动态规划习题完整版
动态规划法求解生产与存储问题
经典的动态规划入门练习题
USACO上面的动态规划题目
动态规划练习题合集(Dp-合集)
几个经典的动态规划问题
动态规划习题
动态规划经典问题
动态规划习题精讲
动态规划部分常见题目
相关主题
文本预览