NOIP普及讲座动态规划从搜索到动态规划

1、从搜索到动态规划第1页点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）设有一个三角形数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，能够向左走或向右走，从根结点13出发向左、向右路径长度能够是：13117147，其和为521311121413，其和为63若要求从根结点开始，请找出一条路径，使路径之和最大,输出路 径长度。1315141124131211876872612第2页点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）【问题分析】（1）贪心法第3页点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）【问题分析】（2）搜索：第4页点击添加文本

2、点击添加文本点击添加文本点击添加文本引例（数塔问题）【问题分析】（3）动态规划： 第5页点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）1315141124131211876872612第6页点击添加文本点击添加文本点击添加文本点击添加文本动态规划基本概念（1）阶段：把所给问题过程，恰当地分为若干个相互联络阶段，方便能按一定次序去求解。（2）状态：状态表示每个阶段开始所处自然情况和客观条件，它描述了研究问题过程中情况。（3）决议：决议表示当过程处于某一阶段某个状态时，能够作出不一样决定（或选择），从而确定下一阶段状态，这种决定称为决议。第7页点击添加文本点击添加文本点击添加文本

3、点击添加文本动态规划基本概念（4）策略和最优策略：由全部阶段决议组成决议序列称为全过程策略，简称策略。 在实际问题中，从决议允许集合中找出最优效果策略称为最优策略。（5）状态转移方程：状态转移方程是确定两个相邻阶段状态演变过程。第8页点击添加文本点击添加文本点击添加文本点击添加文本利用动态规划条件（1）最优化 子问题局部最优将造成整个问题全局最优，即问题含有最优子结构性质。也就是说问题一个最优解中包含着子问题一个最优解。（2）无后效性 当前阶段中状态只能由上一个阶段中状态转移方程得来，与其它阶段状态没相关系，尤其是与未发生阶段状态没相关系，这就是无后效性。 第9页点击添加文本点击添加文本点击添

4、加文本点击添加文本动态规划算法普通模式（1）划分阶段：按照问题时间或空间特征，把问题分为若干个阶段；（2）确定状态和状态变量：将问题发展到各个阶段时所处各种情况用不一样状态表示出来；（3）确定决议并写出状态转移方程：普通是依据相邻两个阶段各状态之间关系来确定决议；（4）寻找边界条件：给出状态转移方程是一个递推式，必须有一个递推边界条件；（5）编写程序。第10页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题1】拦截导弹（noi openjudge 8780）问题描述：某国为了防御敌国导弹攻击，发展出一个导弹拦截系统。不过这种导弹拦截系统有一个缺点：即使它第一发炮弹能够抵达任意

5、高度，不过以后每一发炮弹都不能高于前一发高度。某天，雷达捕捉到敌国导弹来袭。因为该系统还在试用阶段，所以只有一套系统，所以有可能不能拦截全部导弹。输入导弹依次飞来高度（雷达给出高度数据是小于30000正整数），计算这套系统最多能拦截多少导弹。第11页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解输入第一行是一个整数N（不超出15），表示导弹数。第二行包含N个整数，为导弹依次飞来高度（雷达给出高度数据是小于30000正整数）。输出一个整数，表示最多能拦截导弹数。样例输入8389 207 155 300 299 170 158 65样例输出6第12页点击添加文本点击添加文本点击添加文

6、本点击添加文本经典例题讲解【问题分析】状态： fi代表打下第i颗导弹最多能打多少颗导弹方程：fi=max(fj)+1(1=ji)且第i颗导弹高度要高于第j颗导弹高度第13页点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】第14页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题2】饥饿牛问题描述：牛在饲料槽前排好了队。饲料槽依次用1到N(1=N=)编号。天天晚上，一头幸运牛依据约翰规则，吃其中一些槽里饲料。 约翰提供B个区间清单。一个区间是一对整数start-end,1=start=end=N，表示一些连续饲料槽，比如1-3,7-8,3-4等等。牛能够任意选择区间，

7、不过牛选择区间不能有重合。当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多东西。在上面例子中，1-3和3-4是重合；聪明牛选择1-3，7-8，这么能够吃到5个槽里东西。第15页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行，整数B(1=B=1000)第2到B+1行，每行两个整数，表示一个区间，较小端点在前面【输出格式】仅一个整数，表示最多能吃到多少个槽里食物。【样例输入】31 37 83 4【样例输出】5第16页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态： fi代表吃了第i个区间最多能多少食物

8、方程：fi=max(fj)+i个区间长度(1=ji)且第i颗区间开始时间要大于j区间结束时间第17页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题3】最长公共子序列（codevs1408）问题描述：熊大妈奶牛在小沐沐熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。小沐沐说，对于两个串A，B，假如它们都包含一段位置不一定连续数字，且数字是严格递增，那么称这一段数字是两个串公共上升子串，而全部公共上升子串中最长就是最长公共上升子串了。奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，

9、只要告诉奶牛它长度就能够了。第18页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行N，表示A，B长度。第二行，串A。第三行，串B。【输出格式】输出长度【样例输入】42 2 1 32 1 2 3【样例输出】2【数据范围及提醒】 1=N=3000，A，B中数字不超出maxlongint第19页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态 fi,j代表a字符串到i,b字符串到j最长公共字串 方程： ai=aj 则 fi,j=fi-1,j-1+1; ai不等于aj 则fi,j=max(fi-1,j,fi,j-1)第20页点击添加文本点击添

10、加文本点击添加文本点击添加文本【程序实现】第21页点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】第22页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题4】最低通行费用（noi openjudge 7614）问题描述：一个商人穿过一个 N*N 正方形网格，去参加一个非常主要商务活动。他要从网格左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间每个小方格时，都需要缴纳一定费用。这个商人期望在要求时间内用最少费用穿越出去。请问最少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向

11、移动且不能离开网格）。输入第一行是一个整数，表示正方形宽度N (1 = N 100)；后面 N 行，每行 N 个小于 100 整数，为网格上每个小方格费用。输出最少需要费用.第23页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解样例输入51 4 6 8 10 2 5 7 15 17 6 8 9 18 20 10 11 12 19 21 20 23 25 29 33 样例输出109提醒样例中，最小值为109=1+2+5+7+9+12+19+21+33。第24页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：fi,j代表抵达i,j位置最低费用方程：fi,

12、j=max(fi-1,j,fi,j-1)+ai,j;第25页点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】第26页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题5】机器分配 问题描述：某总企业拥有高效生产设备M台，准备分给下属N 个分企业。各分企业若获得这些设备，可认为总企业提供一定盈利。问：怎样分配这 M 台设备才能使国家得到盈利最大？求出最大盈利值。 分配标准：每个企业有权获得任意数目标设备，但总台数不得超过总设备数 M。其中M=100，N=100。 第27页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】 第一行为两个整数M，N。

13、接下来是一个NM矩阵，其中矩阵第i行第j列数 Aij表明第i个企业分配j台机器盈利。全部数据之间用一个空格分隔。 【输出格式】 只有一个数据，为总企业分配这M台设备所取得最大盈利。 【样例输入】3 2 1 2 3 2 3 4 【样例输出】4第28页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：fi,j代表前i个企业分配到j台设备所能取得最大盈利方程fi,j=max(fi-1,j-k+ai,k) 0=k=j第29页点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】第30页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题6】复制书稿问题描

14、述： 有M本书（编号为1，2，M），每本书都有一个页数（分别是P1，P2，PM）。想将每本都复制一份。将这M本书分给K个誊录员（1=K=M=500)，每本书只能分配给一个誊录员进行复制。每个誊录员最少被分配到一本书，而且被分配到书必须是连续次序。复制工作是同时开始进行，而且每个誊录员复制一页书速度都是一样。所以，复制完全部书稿所需时间取决于分配得到最多工作那个誊录员复制时间。试找一个最优分配方案，使分配给每一个誊录员页数最大值尽可能小。（假设复制一页需要1分钟）第31页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行两个整数M、K；（K=M=100）第二行M个整数

15、，第i个整数表示第i本书页数。【输出格式】共1行，复制完全部书最少用时间（分钟）【输入样例】9 31 2 3 4 5 6 7 8 9【输出样例】17第32页点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态fi,j代笔前 i个人写j本书所需要最少时间。方程：fi,j= min(max(fi-1,k,sj-sk) i-1=k=j-1第33页点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】第34页点击添加文本点击添加文本点击添加文本点击添加文本动态规划小结求得一个最优解当前阶段决议仅受前一阶段决议影响，并决定下一个阶段决议当前阶段i多个规划(决议)当前最优决议当前非最优决议i向着目标阶段不停改变(动态)规划方向目标阶段初始阶段动态规划第35页点击添加文本点击添加文本点击添加文本点击添加文本动态规划小结动态规划和普通递推