信息学竞赛中的动态规划专题
哈尔滨工业大学周谷越
【关键字】
动态规划动机状态典型题目辅助方法优化方法
【摘要】
本文针对信息学竞赛（面向中学生的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就可以从次底层
的两个4走来，假设分别知道走到次底层的两个4的最优解，那么取其中较大的加上6就是走到最底层的6时的最优解。然而次底层的两个4还可以走向最底层的2和1，这样就产生了重复的子问题。动态规划的第一类动机就是为了要避免这种重复运算。
事实上，子问题的个数是确定的，只要我们能够把已经计算过的子问题记录下来，再下次需要时直接使用，便可以大大提高程序的效率。
下面介绍一下动态规划的相关概念。首先动态规划是来解决最优化问题的，再进一步说就是解决最优化问题中的多阶段决策问题。
以下是动态的定义内容，在各种基础书籍上都有相关讲解，在此仅列出，不做累述。
状态（State）：表示事物的性质，是描述动态规划中的单元的量。
阶段（Stage）：阶段是一些性质相近的状态集合。
决策（Decision）：每个阶段做出的某种选择性行动，是程序所需要完成的选择。
状态转移方程（Equal）：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是动态规划的核心。
初始状态：由已知能够确定的状态。
目标状态：表示解或能够转化为解的状态。
总体看来，由初始状态经过若干阶段通过若干决策推出目标状态的过程就是动态规划。下面我们就Number Triangles一题对这些概念对号入座：
首先确定状态，用F[I,J]表示从顶层走到第I行第J列的点能取得的最大和。显然每一层为一个阶段。而对于走到每一个非顶层点的情况来说，最多都只可能由它上方的点或左上方的点走来。则有状态转移方程：F[I,J] = Max（F[I-1,J], F[I-1,J-1]）+ A[I,J]；初始状态为F[1,1] = A[1,1]；目标状态为F[N,K]，其中K∈[1,N]。要求输出的解则是Max {F[N,K]} ，其中K ∈[1,N]。时空复杂度均为O（N2）。
这里给出程序主干部分：
F[1,1] = A[1,1]
For I = 2 to N Do
For J = 1 to I Do
If F[I-1,J] > F[I-1,J-1] Then
F[I,J] = F[I-1,J] + A[I,J]
Else
F[I,J] = F[I-1,J-1] + A[I,J]
接下来我们从理论上来讨论使用动态规划的条件。对于一种状态划分的方法来说，状态只与状态本身的性质有关，而与如何达到该状态等其他条件一概无关的性质叫做无后效性。由于存在无后效性，决策只能从决策本身的性质来确定，使得某一阶段的状态只与它所在阶段的前一阶段的状态有关。可以看出，存在无后效性是应用动态规划的前提条件。而考虑动态规划的正确性时，问题则需要满足最优子结构。所谓最优子结构，即当前一阶段的状态最优时，通过状态转移方程得到的状态也能达到最优。理论上看，无后效性和最优子结构是使用动态规划时的两个基本条件，而具体应用动态规划时更多凭借的是经验。
下面再引出一道经典题目做一下分析：
ACM/ICPC Shanghai2001 Skiing
http://122.139.62.222/problem.php?id=1862
【题目描述】
滑雪是一项很受欢迎的体育运动，为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡。我们想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
我们可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
【输入格式】
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 500)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
【输出格式】
输出最长区域的长度。
【样例输入】
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
【样例输出】
25
有了前面的例子，不难看出，每个点可以由四个方向中比它高的点滑到。设DX = {0,1,0,-1}，DY = {1,0,-1,0}，F[I,J]表示滑到第I行第J列的点时存在的最长滑坡长度，则有状态转移方程：F[I,J] = Max{F[I+DX[K],J+DY[K]]}+ 1，其中要求满足第I+DX[K]行第J+DY[K]列的点存在且高度比第I行第J列的点的高度高。我们可以按照深度优先搜索的方式计算F，并利用二维数组Arr记录计算过的F值，下面同样给出程序主干部分：
Function F (Int I, Int J)
{
If Arr[I,J] > 0 Then
Return Arr[I,J]
Int P, Ans = 0
For P = 1 to 4 Do
If ((I+DX[P],J+DY[P]) In Map) And (H[I+DX[P],J+DY[P]] > H[I,J]) Then
If (Ans < F[I+DX[P],J+DY[P]])
Ans = F[I+DX[P],J+DY[P]]
Arr[I,J] = Ans + 1
Return Arr[I,J]
}
同样是动态规划，是什么使得两道题目代码的主干部分相差巨大呢？这里讨论一下动态规划的两种实现形式——递推和记忆化搜索。首先，可以说所有用递推实现的动态规划均可以利用记忆化搜索实现。而某些题目之所以可以用递推求解，是因为这类题目同一阶段的状态表示上有很大的相关性，比如数字矩阵中某一行或列，这使得我们可以计算一个阶段的所有状态后再计算下一状态。而某些题目中利用动态规划划分的同一阶段的状态表示上没有多大相关性，比如Skiing里面的状态，从某点做起点每滑动一步为一个阶段，我们无法用一个准确的可以直接利用的集合将一个阶段中的状态表示出来，只能从已知状态去找和它相关联的状态。对于Skiing我们已知的是目标状态（即四面都不比该点高的点），通过边界条件（即四面都比该点高的最优值为1），便可以进行记忆化搜索。
利用递推实现动态规划时，单位操作时间小，可以方便地使用一些优化；而利用记忆化搜索实现动态规划时，单位操作时间大，但可以避免计算一些不必要的状态。总地来说，相比于用状态空间搜索的方法解决这类存在重复子问题的题目，使用动态规划增大了空间的开销，但提高了时间效率。
1.2 解决复杂贪心问题
接下来，进入下一话题。我们考虑一下我们熟知的贪心算法和动态规划的关系，我看过很多写贪心算法和动态规划之间区别的材料，在这里我们不谈这个，而是要讨论动态规划与贪心算法之间的联系。
如果我们把每一步贪心作为一个阶段，那么可以认为每个阶段只有一个状态，再把贪心策略看作状态转移方程，那么这样是否也是一种“动态规划”呢？实际上，它们二者之间的差别就在数据的维护上，有很多贪心问题在采取一次贪心策略之后要对数据进行全盘的维护，而我们讲的动态规划一般没有这个步骤。
而这个维护的目的是什么呢？是为了保证正确性，和动态规划中的最优子结构的目的一样，那么就说明目前的状态划分不具有最优子结构，那么我们是否能够通过改变状态的划分方法来代替这个维护并使新划分的状态具有最优子结构呢？这里直接给出结论：对于某些分步讨论的贪心决策问题，我们可以通过扩展状态使之能够用动态规划解决。扩展出的状态的作用就是为了保证正确性，也就是保证最优子结构。
举一个简单的例子：给出N个数，要从其中取M个求和，并使和尽量大。这明显是一个贪心可解的问题，把数字从大到小排序后取前M个求和即可。那么我们同样也可以扩展出一部分状态。我们设F[I,J]表示前I个数字中取了J个数字得到的最大和，则有：F[I,J] = Max (F[I–1,J],F[I-1][J-1] + A[J])。那些贪心算法并不用考虑的“多余”状态就是扩展出的状态，举个实例来说明：N = 5 , M = 3时，A[] = {1, 2, 3, 4, 5}。那么显然1和2都不会被取到，但数组F中的F[1,1], F[2,1] 和F[2,2]都是由1和2组成的状态，从贪心的角度看，它们就是多余的，就是为了使用动态规划扩展出来的状态。当然，就这道题目来看，贪心算法无论是从
思维角度、编程角度还是时空复杂度角度都明显优于动态规划。
HCPC Spring 2007 Hurdles Race
https://www.doczj.com/doc/0a8336232.html,/hoj/problem/view?id=2476
【题目描述】
自从刘翔在雅典夺得110米栏冠军之后，国人对跨栏比赛的关注程度大大提高。
阿月和同学们经常在一起讨论刘翔需要用多少步来完成比赛，大家对该问题的意见不太一致，经常为此争论不休。
我们下面定义这样一种跨栏比赛：
tl表示起点到终点的距离（可能不是110）；
sl表示刘翔一步可以跨越的最大距离（我们规定刘翔每次跨越的距离必需是整数）；
fl表示第一个栏到起点的距离（fl n表示栏的数目； d表示每两个栏之间的距离（我们保证最后一个栏到起点的距离小于tl）； 每次跨栏的时候，刘翔都要保证栏的位置恰好在他跨越距离的正中间。 求在这些条件下刘翔完成比赛所需要的最小步数。 【输入格式】 输入包括五个正整数，分别表示tl,sl,fl,n,d（tl不超过10000，sl不超过10）。 【输出格式】 输出包括一个整数，即刘翔完成比赛所需要的最小步数。 【样例输入】 110 3 20 10 5 【样例输出】 41 【样例说明】 起点到跨过第一个栏至少需要8步，之后每跨一个栏至少需要2步，从跨过最后一个栏到终点至少需要15步。 由于只有跨栏的那步有限制条件，其它步没有，故有了贪心思想——跨栏那步要尽可能的大。通过分情况讨论后得到解：跨第一个栏之前的步数 + 栏的个数 + 跑2个栏之间路程需要的步数×（栏的个数 - 1） + 最后一个栏需要的步数。需要考虑的特殊情况只有跨第一个栏的步长未必可以达到跨其它栏的步长。 当然，如果比赛的时候可以快速地想到这个方法是最好不过的。实际上，使用动态规划更容易建立方程。设F[I]表示到达i位置所需要的最小步数，则有F[i]=min{F[I-K]+1}，K=1..sl，其中I-K到I之间没栏；而有栏时，F[I]=min{F[I-2*sp]+1,F[I]}，sp为栏到i点距离。 AsyzOI2007 营养膳食 http://122.139.62.222/problem.php?id=1864 【题目描述】 阿月正在女朋友宁宁的监督下完成自己的增肥计划。 为了增肥，阿月希望吃到更多的脂肪。然而也不能只吃高脂肪食品，那样的话就会导致缺少其他营养。阿月通过研究发现：真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说，肉类不宜吃超过1份，鱼类不宜吃超过1份，蛋类不宜吃超过1份，蔬菜类不宜吃超过2份。阿月想要在营养膳食的情况下吃到更多的脂肪，当然阿月的食量也是有限的。 【输入格式】 输入第一行包含三个正整数n（n≤200）,m（m≤100）和k（k≤100）。表示阿月每顿饭最多可以吃m份食品，同时有n种食品供阿月选择，而这n种食品分为k类。第二行包含k个不超过10的正整数，表示可以吃1到k类食品的最大份数。接下来n行每行包括2个正整数，分别表示该食品的脂肪指数ai和所属的类别bi，其中ai≤100，bi≤k。 【输出格式】 输出一个数字即阿月可以吃到的最大脂肪指数和。 【样例输入】 6 6 3 3 3 2 15 1 15 2 10 2 15 2 10 2 5 3 【样例输出】 60 用贪心算法解决，就是把食品按脂肪指数排序后，在满足约束条件的情况下从大的开始吃，每吃一个更新一下约束条件。而用动态规划思想解决的话，可以设F[I,J]表示前I类食品一共吃J份能够获得的最大脂肪数和。则有F[I,J] = Max {F[I-1,K] + G[I,J-K]}，其中G[I,J]表示第I类食品种脂肪数最大的J份的和（也是要排序的）。 Noip1999 旅行家的预算 http://122.139.62.222/problem.php?id=1523 【题目描述】 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）。每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=l,2,...,N）。 如果无法到达目的地，则输出“No solution”。否则输出最小费用，计算结果四舍五入至小数点后两位。 【样例输入】 275.6 11.9 27.4 2.8 2 1 102.0 2.9 2 220.0 2.2 【样例输出】 26.95 我们假设现在在第I站，那么可知在该站加满油可以到达的最远距离。如果在这个范围内存在一个加油站J，它的价格比I便宜，那么只要把油加到刚好能到达第一个出现的J即可；否则就在I加满油，选择范围内最便宜的加油站J，开到J再做决策。如果觉得这个方法不是很好想的话，就用动态规划实现之。设F[I,J]表示到达第I个加油站油量为J需要的最小费用，则有F[I,J] = Min {F[I-1, J-K-G(I-1,I)] + K*A[I]}，其中G(I-1,I)表示第I个加油站和前一个加油站间的距离，A[I]表示第I个加油站的油价。 对于以上三道题目，实现贪心更容易，而想到动态规划更容易（前提是对动态规划足够熟练），可以根据实际情况选择合适的算法。下面再给出两个相对复杂的题目。 AsyzOI2005 雇工 【题目描述】 一中搬到新校舍，值得庆祝。但我们亲爱的电教老师FJ（Feng Jun not Farmer John）却遇到了个麻烦事。科技馆还没完全建好，需要雇人来完成一些后续工作。现在的行情是这样的：你雇佣一个人得给A元，解雇一个人得给人家B元（精神损失费），当然还有工资，每月K元。有一系列工作，需要N月来完成。当然，不是每个月都需要相同的人数。可是当你雇佣一个雇工，不管他干不干活，都得给他工资（吃大锅饭）。说明一下：到期的时候是不用付精神损失费的。 请你帮帮FJ老师，他心系学校，绝对要为一中省钱。 【输入格式】 输入包含三行。第一行为N（不大于12的正整数）。第二行有三个数，A，K，B （J 均不大于100）。第三行为每个月需要的最少人数（均小于1000）。 【输出格式】 输出包括一个数字即最小费用。 【样例输入】 3 4 5 6 10 9 11 【样例输出】 199 考虑每一个月，比较当前的工人数M1和下一个月所需要的工人数M2，若M1≤M2，则必须雇佣缺少的工人，当然也不会多雇。问题的关键就在于可以解雇的时候解雇多少工人，可以认为对于一组给定的A,K和B就可以得到一个吃大锅饭的最长时间（超过该时间可以解雇了后再雇佣），这样我们找到这个时间内的最大工人需求量M3，若M1≤M3，那么不用解雇任何工人，否则就要解雇M1 - M3个工人。需要注意的是，判断最长时间时需要考虑到期的时候不付精神损失费的特殊情况。 而采用动态规划则要简单得多。设F[I,J]表示完成了前I个月的工作任务且第I个月有J 个工人所需的最小费用，则有F[I,J] = Min {F[I-1,H] + G(H,J) + K*J}，其中G(H,J)表示由H 个工人变化到J个工人所要支付的费用（或雇佣或解雇）。使用动态规划来解决这道题目，无论从思路还是实现来说都要比贪心算法简单。 在有规定时间限制的竞赛中，做题的速度也很重要。这催生了我们使用动态规划的第二个动机——解决复杂的分步讨论的贪心决策问题。但仅限于数据范围不大的情况，因为较比贪心算法，动态规划的时间复杂度要大一些。总地来说，这类动态规划牺牲了程序的时空效率，但思维和编程比较简单，可以节约宝贵的竞赛时间。 2.动态规划的状态划分方法 在这里我们把动态规划状态的划分方法分为3种：一维状态划分、二维状态划分和树型状态划分。树型动态规划是由于树这种数据结构的特殊性衍生出来的（放在最后说），这里先讨论一下一维状态划分和二维状态划分的动态规划。 前面提到的动态规划基本都属于一维状态划分，以Number Triangles的方程为例（F[I,J]表示从顶层走到第I行第J列的点能取得的最大和）。定义I为阶段变量，J为状态变量（我为了自圆其说，方便讲解，自己定义的），阶段变量可以确定状态所在阶段，而状态变量则反映状态本身的性质。允许只有阶段变量没有状态变量，例如Hurdles Race里的F[I]。而前面提到的二维状态划分只有Skiing一题（F[I,J]表示滑到第I行第J列的点时存在的最长滑坡长度），因为这里I和J两个变量才能确定状态所在的阶段。 2.1.1 典型的线性动态规划 我们通常说的线性动态规划就是一维状态划分的没有状态变量的动态规划。下面了列举几个典型的线性动态规划题图： UV A 10684 The Jackpot 【题目描述】 某人想迅速变得富有，但是他还不想工作。于是他开始赌博，存在一个奖金序列（有正有负），他想从中赢得最多的钱，我们规定他中途只可以退出一次（退出后不可以再回来）。 【输入格式】 输入第一行包含一个正整数N（N≤10000），接下里包含N个整数，它们的绝对值都不超过1000。 【输出格式】 输出该人能赢得的最大钱数。 【样例输入】 5 12 -4 -10 4 9 【样例输出】 13 我们称该类问题为最大连续数字和。设F[I]表示到I为止（必须含A[I]）的最大连续整数和，如果F[I-1]为负数，那么显然F[I] = A[I]，否则有F[I] = F[I-1] + A[I]。这样就构造出一个线性动态规划算法了，以下是它的一个经典应用： NECPC2007 Sum Of SubRectangular Parallelepiped https://www.doczj.com/doc/0a8336232.html,/index.php?act=problem&id=1229 【题目描述】 现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。 【输入格式】 第一行包含一个整数n。接下来n个n2的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整数值。 【输出格式】 输出仅包括最大的长方体的数和。 【样例输入】 2 1 2 2 1 -1 –2 -2 -1 【样例输出】 6 最基础的方法是“直译”枚举过程，时间复杂度O（n9）。而记录先前考察的结果。如图所示，在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。经过这样的优化， 利用了前面的计算结果，时间复杂度降为O（n8）。 而对于每个平面的矩形有一种经典的压缩方 法，设rec[x,y,z]表示z轴坐标为z的水平面中矩形 （1,1,x,y）的数和。则z轴坐标为z的水平面中左 上角为（x1,y1）、右下角为（x2,y2）的矩阵的数 和为rec[x2,y2,z] + rec[x1,y1,z] - rec[x2,y1,z] - rec[x1,y2,z]。 有了上面的关系式，我们下面要做的只是枚举z,x1,x2,y1,y2来查找最优解。对于每组固定的x1,x2,y1,y2，rec[z, x1,x2,y1,y2]就等于z个数字，那么只要求它们的最大连续和就可以。总的时间复杂度为O（n5）。 Noip2004 合唱队型 【题目描述】 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的 身高分别为T1，T2，…，TK，则他们的身高满足T1<... 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入格式】 第一行是一个整数N(2≤N≤106)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130≤Ti≤230)是第i位同学的身高(厘米)。 【输出格式】 只包含一个整数，就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 首先只考虑左半部分的合唱队型，这种题目类型叫做最长上升子序列问题（LIS），最常规的算法是设F[I]表示前I个数字中（必须包含A[I]）的最长上升子序列的长度，状态转移方程为F[I] = Max {F[J] + 1}，其中J∈[0,I-1] 且A[J] < A[I]。I和J都需要枚举，所以时间复杂度为O（n2）。 实际上LIS有一种贪心算法，我们用数组G[I]记录当前长度为I的上升子序列的最后一个元素的最小值，那么G[I]将会是一个单调的序列。对于每一个A[J]，只要在G序列中找到一个最大的I，使得G[I] < A[J]，那么就可以在它的后面插入A[J]就形成了当前的最长上升子序列，接下来需要更新G（当然只是其中的一个元素）。对于顺序表G的查找可以使用二分查找，这样整个算法的时间复杂度为O（nlogn）。 另外值得一提的就是在解决合唱队型这个问题时，不要枚举分割点之后再分别向两个方向动态规划，那样的时间复杂度为O（n2logn）。比较明智的做法是分别向两个方向动态规划，再枚举分割点，直接做加法计算即可，时间复杂度为O（nlogn）。 2.1.2 其他线性动态规划举例 很多其他的线性动态规划基本都是大同小异，它们的共同点就是沿着一个轴（如坐标轴、时间轴）进行规划；由于没有状态变量，它们的状态就是用F[I]表示到轴上第I个点为止的题目所要求的最优解。接下来再举两个例子加以说明。 USACO 3.1.2 Score Inflation http://122.139.62.222/problem.php?id=1441 【题目描述】 学生在我们USACO的竞赛中的得分越多我们越高兴。 我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。 我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。 你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。 【输入格式】 输入包括竞赛的时间，M(1≤M≤10,000)和N，“种类”的数目（1≤N≤10,000）。后面的每一行将包括两个整数来描述一个“种类”，第一个整数说明解决这种题目能得的分数(1 ≤points≤10000)，第二整数说明解决这种题目所需的时间（1≤minutes≤10000）。 【输出格式】 只包含一个整数，就是在竞赛的时间中得到最大的分数。 【样例输入】 300 4 100 60 250 120 120 100 35 20 【样例输出】 605 很容易写出线性动态规划方程：设F[I]为到时间I为止任意安排题目可得的最多分数。则F[I] = Max {F[I-A[J]] + B[J]}，其中A[J]为第J类题目的时间，B[J]为第J类题目可得分数。时间复杂度为O(M N)，在1s的时限内难以出解。 事实上，很多种类的题目是废题（用时多，得分少）。我们可以用一些特殊的数据结构找出这些废题，并不在动态规划的时候考虑它们，但我们也可以用性价比（得分/用时）来大略地衡量某种题目的好坏。如果我们只取性价比最好的前K种题目，那么动态规划的时间复杂度就为O(MK)。实践证明，取K = 150时已经可以通过全部测试数据。 Noip2005 过河 http://122.139.62.222/problem.php?id=1571 【题目描述】 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 【输入格式】 第一行有一个正整数L（1≤L≤109），表示独木桥的长度。第二行有三个正整数S，T， M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1≤S≤T≤10，1≤M≤100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 【输出格式】 只包括一个整数，表示青蛙过河最少需要踩到的石子数。 【样例输入】 10 2 3 5 2 3 5 6 7 【样例输出】 2 看到题目首先想到的是时间复杂度为O(TL)的线性动态规划。设F[I]表示青蛙跳到I点时所踩的最小石子数，则有F[I] = Min{F[I-K] + A[I]}。但是L的上限为109，这种算法显然是不行的。仔细思考，可以得到下面的结论：存在N0，当n > N0时，n可以由若干S到T 之间的正整数（包括S，T）组成。因此，将障碍点按升序排列，当两相邻障碍点之间距离较大时，可适当缩小两障碍点之间距离，但不影响最终结果。（特别地，当S=T时需要单独处理） 针对每一组S和T都存在一个N0。对于任意的S和T（S≠T时），那么每次至少有T 和T-1两种跳法。假设青蛙跳T次，其中K次跳T步，T-K次跳T-1步，那么总步数为KT + (T-K)(T-1)= T(T-1) + K，也就是说T(T-1)以外的所有点都可以跳到。这样一来，我们就可以把间距超过T(T-1) + K的两点间距离化为T(T-1) + K。T=K=10时，T(T-1) + K取得最大值100，这时整个算法的时间复杂度为O(100MT)，可以在1s内通过全部测试数据。 2.1.3 一维状态划分的非线性动态规划 下面要讨论的是一维状态划分的非线性动态规划问题。其中最为经典的模型就是0-1背包问题：给定N种物品和一背包。物品I的重量是WI，其价值为VI，背包的容量为C。选择装入背包的物品，使得装入背包中物品的总价值最大，求这个最大价值。 每考虑一件物品为一个阶段，对于每一物品来说，都只有取和不取两种可能。那么设F[I,J]表示考虑前I个物品取的总重量不超过J的最大价值，则有状态转移方程：F[I,J] = Max （F[I-1,J], F[I-1,J-WI] + VI）。实际上，0-1背包问题和Number Triangles问题只是在做决策时略有不同，前者考虑取或者不取，而后者考虑要走到左边还是右边。最后提醒一下，0-1背包是一个NP问题，时空复杂度均为O（NW），当W的规模比较大时（不是很过分的大），空间开销随之增大，我们可以利用滚动数组解决这一问题。由于动态规划的无后效性，我们只需记录相邻的两个阶段的状态即可，这就是滚动数组的原理。 Noip2006 金明的预算方案 http://122.139.62.222/problem.php?id=1579 【题目描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞 的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过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]。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。 【输入格式】 第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是所属主件的编号） 【输出格式】 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。 【样例输入】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【样例输出】 2200 题目已经提示我们每个主件可以有0个，1个或2个附件。那么考虑每套主件与附件的组合，最多有5种处理方法：不取，主件，主件+附件A，主件+附件B和主件+附件A+附 件B。设F[I,J]表示前I种组合花费为J获得的最大重要度乘积和，则有：F[I,J] = Max ( F[I-1,J], F[I-1,J-V[I,0]]+V[I,0]*W[I,0], F[I-1,J-V[I,0]-V[I,1]]+V[I,0]*W[I,0]+V[I,1]*W[I,1], F[I-1,J-V[I,0]-V[I,2]]+V[I,0]*W[I,0]+V[I,2]*W[I,2], F[I-1,J-V[I,0]-V[I,1]-V[I,2]]+V[I,0]*W[I,0]+V[I,1]*W[I,1]+V[I,2]*W[I,2]) 还可以利用“每件物品都是10元的整数倍”的条件，总的时间复杂度为O（NM）。 NoiWC2007 Hotel 【题目描述】 有N个男人，M个女人，其中有C（1≤C≤M,N≤500）对夫妇要住房。现在有P（P ≤500)个房子。每个房子有个费用Ci和床位Bi（Bi≤5）。住房有以下要求： 1.每个房子住的人数不能超过Bi 2.一个房间住了夫妇，不能再住其他人。 3.不考虑夫妇情况下：一个房间住了男人后，不能再住女人。对女人也是一样。 求这N+M个人住房的最少费用。 【输入格式】 第1行为四个正整数，N,M,C和P。以下P行每行包含两个正整数Ci和Bi。 【输出格式】 只有一个正整数，为这N+M个人住房的最少费用（longint范围内）。 【样例输入】 3 2 2 4 30 4 20 1 10 2 20 2 【样例输出】 40 事实上我们可以发现按照第2条住房的夫妇数不会超过1，如果有2对夫妇那么可以交换一下，在同样代价下反而能住更多人。这样我们可以枚举夫妇数（0或者1），这样就去掉了夫妇的这个限制。 设F[I,J,K]表示前I个房间安排好后，还剩下J男K女的最小费用。则显然有F[I,J,K]=Min {F[I-1,J,K], F[I-1,J+B[I],K]+C[I], F[I-1,J,K+B[I]]+C[I]}，时间复杂度为O(P M N)。和前面说过的Score Inflation一样，在人数比较多的时候可以加入贪心思想。当人数超过R的时候，性价比比较高的房间就必然会被使用，那么先把所有房间按照性价比排序然后按顺序分放直到人数少于R为止，时间复杂度就降为O(P R2)。 Shanghai2004 The Horse Racing http://122.139.62.222/problem.php?id=1865 【题目描述】 中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马（N≤2000），每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢最多的钱？ 【输入格式】 第1行为一个正整数N。第2行和第3行每行包含N个正整数，分别表示田忌和齐王帐下马的速度。 【输出格式】 只有一个正整数，即田忌能赢得的最大钱数。 【样例输入】 3 92 83 71 95 87 74 【样例输出】 200 这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边，把齐王的马放右边。田忌的马A和齐王的B之间，如果田忌的马胜，则连一条权为200的边；如果平局，则连一条权为0的边；如果输，则连一条权为－200的边，但二分图最佳匹配算法的复杂度为O（N3）。 因为田忌掌握有比赛的主动权，他总是根据齐王所出的马来分配自己的马，所以这里不妨设齐王的出马顺序是按马的速度从高到低出的。 对于这样的假设，我们归纳出如下贪心策略： 1.如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马； 2.如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马； 这两点是显然的，关键在于田忌最快的马和齐王最快的马打平，那么田忌是选择平还是输呢？ 如果全部打平的话，如果齐王马的速度分别是1 2 3，田忌马的速度也是1 2 3，每次选 择打平的话，田忌一分钱也得不到，而如果选择先用速度为1的马输给速度为3的马的话，可以赢得200两黄金。而如果全部输掉的话，如果齐王马的速度分别是1 3，田忌马的速度分别是2 3，田忌一胜一负，仍然一分钱也拿不到。而如果先用速度为3的马去打平的话，可以赢得200两黄金。 这里虽然出现了分支，但我们得知田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。那先把田忌和齐王的马分别按从强到弱排序，设F[I,J]表示齐王按从强到弱的顺序出马和田忌进行了I场比赛之后，田忌从头取了J匹较强的马出战所能够得到的最大钱数。则有：F[I,J] = Max {F[I-1,J] + G[N-(I-J)+1,I],F[I-1,J-1]+G[J,I]}，其中G[J,I]表示田忌的第J匹马和齐王的第I匹马比赛的获利。 2.1.4 压缩状态的动态规划 下面介绍一下压缩状态的动态规划。这种动态规划的本质是对集合进行动态规划，对于给出的数据在某一个或几个维度上一般具有比较小的范围（可以枚举一类的状态），我们把一个枚举出的状态视为一个集合，通过它们之间的关系（产生式规则）可以进行动态规划。 当集合中元素个数的不定性或范围大时，如果直接开数组存，索引数组的编程复杂度太高（而且程序时间效率低下），所以要进行集合编码。一般利用数据的可枚举性，采用进位制的方法进行状态压缩。下面举一个经典的问题作为例子： Noi2001 炮兵阵地 【题目描述】 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 【输入格式】 第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。 【输出格式】 仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。 【样例输入】 5 4 PHPP PPHH PPPP PHPP PHHP 【样例输出】 6 这是一道比较麻烦的问题，如果某点是P，就可以有放兵与不放兵两种方案，但对于在I和J位置之前的所有P的摆放方案有多种方案，我们将这两种方案分别去尝试与P(I,J)之前所有方案结合，则P(I,J)又会有很多种方案。 考虑一个列为10（M的最大值）的表。即使是一个全为P的空列上一共也只有60种合法的炮兵放置方法。具体对一个列数为10的PH表而言，对每一列也只有前两列对其产生影响，我们设F[I,X,Y]来表示第I-1行处于第X种状态，第I行处于第Y种状态时，从首行扫描到该行时所能存放的最多的炮兵数。则有F[I,X,Y] = Max{F[I-1,Z,X] + N[Y]}，其中要求没有互相攻击的可能，N[Y]表示方案Y对应的炮兵数。 很多状态压缩动态规划是用二进制存储状态，比如有1到10共10个点，需要把它们都走一遍，走过1,2,3点的路径可以用[0000000111]2=[7]10表示，而走过1,2,3,5的路径可以用[0000010111]2=[23]10表示。下面我们用位运算建立它们之间的联系，需要使用异或运算符（^），[0000010111]2^[0000010000]2=[0000000111]2，即23^(1<<(5-1)) = 7，这大大方便了我们在状态压缩动态规划中进行状态转移。下面再举一个例子： HCPC Spring 2007 FishCanFly 【题目描述】 fish is not a common fish, he has a dream that he can fly someday. One day his friend wolfshow tells him a tale. "It is said that there lives a magic bailey in the remote mountains. He can enable some fish to fly once a year. Every year many fish arrive at bailey's house. The lucky fish is the one who has the highest score(what a bad thing!). There are several posthouses on the way to bailey's house. One can get some score when he enters it. But if you enter the same posthouse several times, you can get the score only once. You must remember that the total time is limited. So if you can't get there in time, you will lose it." Luckily, with another friend angela's help, fish gets the map. But he can't calculate the travel path that makes him the lucky fish. Fortunately, you are kind enough to help him, and what you need only to do is the calculation. 【输入格式】 Each test case starts with a single integer n (2 <= n <= 11) denoting the number of posthouses. The posthouses are numbered from 1 to n. Then a matrix with n+2 rows and n+2 columns followes. The integer in row i(row j) and column j(column i) is the time fish will cost to travel between place i and place j directly. A zero means that there is not a direct way connecting place i and j. fish starts with place 0 and bailey's house is at place n+1. The next line contains n integers which indicate the scores at each posthouse. Then followes an integer number denoting the time limit. 【输出格式】 If fish can arrive at bailey's house in time, please output "Fish can fly!" and the highest score he can get separated by just one space. If he can't arrive in time no matter which path he takes, just ouput "Miss bailey!". See the examples for further clarification. 【样例输入】 3 0 2 0 0 0 2 0 3 0 0 0 3 0 8 1 0 0 8 0 0 0 0 1 0 0 1 2 3 【样例输出】 Fish can fly! 6 首先利用Floyed求出最短路，然后进行状态压缩的动态规划。设F[I,S]表示在第I个点，经过路径为S的最少时间，则有：F[I,S] = Min {F[J,S^(1< 2.2.1 典型的二维状态划分的动态规划 下面我们开始讨论二维状态划分的动态规划，这类题目需要使用两个变量确定一个状态的阶段。首先介绍一个经典问题：最长公共子序列（LCS）。将两个给定字符串分别删去零个或多个字符后得到的长度最长的相同字符序列。例如，字符串abcabcabb与bcacacbb的最长公共子序列为bcacabb。LCS问题就是要求两个给定字符串的最长公共子序列的长度。 我们每考虑一个相同的字母为一个阶段，对于每一个相同的字母来说，都可以在它以前最大长度的基础上加1。F[I,J]表示第1个字符串前I个字符和第2个字符串前J个字符的最长公共子序列的长度，则有状态转移方程： F[I,J] = F[I-1,J-1] + 1, 其中A[I] = B[J]； 例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)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么 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），输入称为输入状态，输出称为输出状态。 动态规划练习题 [题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. 样例输入: 样例输出： 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中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品） 信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的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就可以从次底层 动态规划 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。 一、关键子工程（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、硬币问题 最短路径问题 下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。 现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiS［x］为城市x到城市E的最短路径长度（x表示任意一个城市）； map[i，j]表示i，j两个城市间的距离，若map[i，j]=0，则两个城市不通； 我们可以使用回溯法来计算DiS［x］： var S：未访问的城市集合； function search(who{x})：integer； {求城市who与城市E的最短距离} begin if Who＝E Then Search←0 {找到目标城市} Else begin min←maxint；{初始化最短路径为最大} for i 取遍所有城市 Do if（map[Who，i]＞0{有路}）and（i S{未访问}） then begin S←S－[i]；{置访问标志} j←map[Who，i]+ search(i)； {累加城市E至城市Who的路径长度} S←S＋[i]； {回溯后，恢复城市i未访问状态} if j＜min Then min←j； {如果最短则记下} end；{then} search←min；{返回最短路径长度} End；{else} End；{search} begin S←除E外的所有城市； Dis[a]←search（a）；{计算最短路径长度} 输出Dis[a]； end．{main} 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O（n！），这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？ 动态规划（生产和存储问题） 一、动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解 创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。 二、动态规划法基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段 阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=1.2….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动态规划例题
动态规划讲解大全(含例题及答案)
动态规划习题答案
动态规划习题
动态规划练习试题和解答
动态规划典型例题
动态规划习题完整版
动态规划法求解生产与存储问题
经典的动态规划入门练习题
动态规划习题精讲
动态规划试题
动态规划练习题合集(Dp-合集)
几个经典的动态规划问题
动态规划习题
动态规划经典问题
动态规划：最短路径问题及程序
动态规划(生产和存储问题)
相关主题
文本预览