tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

动态规划


动态规划在信息学奥赛中的应用 吴孝燕 一、动态规划的基本思想 动态规划策略通常用于求解具有某种最优性质的问题。动态规划法与分治法类似,其基 本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到 原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不 是互相独立的而是重叠的。动态规划法的基本思路:保存已解决的子问题的答案,而在需

要 时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间;可以用一个表来记录 所有已解的子问题的答案;不管该子问题以后是否被用到,只要它被计算过,就将其结果填 入表中。具体的程序中一般用数组来记录子问题的答案。 二、动态规划问题的特征 适合采用动态程序设计方法的问题特征:最优子结构性质和子问题重叠性质。1、最优子 结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。2、重叠 子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题 被反复计算多次。动态规划法正是利用了这种子问题的重叠性质,对每一个子问题只解一次, 而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。 三、设计动态规划法的步骤及程序流程的一般形式 设计动态规划法的一般步骤:1、找出最优解的性质,并刻画其结构特征; 2、递归地定 义最优值(写出动态规划方程);3、以自底向上的方式计算出最优值;4、根据计算最优值 时得到的信息,构造一个最优解。 为了具体的表示流程引入一些名称。1、阶段 k:按问题的特点划分成需要作出选择的如 干伦次;2、状态 u:某一阶段的出发位置;3、决策 x:在对问题的处理中作出的每种选择性 的行动。 程序流程的一般形式: for k:=阶段最小值 to 阶段最大值 do for u:= 状态最小值 to 状态最大值 do for x:= 决策最小值 to 决策最大值 do begin I[uk]:=min (或 max)(I[uk-1]+l[uk-1 ,xk-1]) {动态规划方程的一般形式} End; 上述程序流程仅提供了自下而上方式解题的一种方法,具体题目还要具体分析,根据题

目问题条件来编程序。 四、动态规划在往年奥赛题中的应用 2000 年 题二 乘积最大

问题描述: 今年是国际数学联盟确定的“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 题目分析: 很明显的动态规划题。用具体的数据来分析。假设输入数据:6 3 284563 我们来分析第 3 个*可以放的位置,它只能放在 4563 这部分数字之间。假设前面两个*已 经放好 2*8*4563 ,第 3 个*可以放 2*8*4*563 或 2*8*45*63 或 2*8*456*3,显然 2*8*45*63 最大, 第 3 个*已经放好;再放第 2 个*,只能在 2*845*63 的 845 这部分数字之间放第 2 个* 的位置,2*8*45*63 或 2*84*5*63,显然 2*84*5*63 大,第 2 个*已经放好;最后放第 1 个*, 它只能放在 284 这部分数字之间,同理显然 2*84*5*63 大。乘积最大是:2*84*5*63=52920 通过以上具体数据的分析推广到 n,假设在 s1?si(2<=I<=n)中插入 j 个*,其中在 s1?sk 中插入了 j-1 个* (j<=k<=I-1):s1*s2*s3?sk*sk+1sk+2?si 设 ans[I,j]为长度是 i 的数串中插入 j 个*的最大乘积。显然 ans[I,0]= s1?si 对应的

整型数组;ans[I,j]=max(ans[I,j], ans[k,j-1]*sk+1sk+2?si) (1<=I<=n,1<=j<=min(I-1,m)); 输入 n,m 和数串 s; for I:=1 to n do ans[I,0]<- s1?si 对应的整型数组; for I:=2 to n do for j:=1 to min(I-1,m) do for k:=j to I-1 do begin q<- sk+1sk+2?si 对应的整型数组; ans[I,j]:=max(ans[I,j], ans[k,j-1]*sk+1sk+2?si); end; 输出 ans[n,m] 本题考查了高精度乘法和动态规划法。高精度乘法部分不用多讲了,请读者自己写。 题四 方格取数 问题描述: 设有 N*N 的方格图(N<=8),我们将其中的某些方格中填入正整数,而其他的方格中则放 人数字 0。如下图所示(见样例 ,黄色和蓝色分别为两次走的路线,其中绿色的格子为黄色 和蓝色共同走过的): A 1 6 3 7 1 4 2 4 1 1 5 1 4 B 某人从图的左上角的 A 点出发,可以向下行走,也可以向右走,直到到达右下角的 B 点。 在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 0)。此人从 A 点到 B 点共走两次,试找出 2 条这样的路径,使得取得的数之和为最大。 输入: 输入的第一行为一个整数 N(表示 N*N 的方格图),接下来的每行有三个整数,前两个表 示位置,第三个数为该位置上所放的数。一行单独的 0 表示输入结束。 输出:

只需输出一个整数,表示 2 条路径上取得的最大的和。 样例: 输入 8 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 输出 67 题目分析: 本题是典型的多维动态规划。 1)当两个人路线有交叉的时候,改成等效的,不交叉的。 如下图,1 代表第一个人,2 代表第二个人。X 代表相遇点。 X111 2 1 222X2 12 12 1X1 2X 变成: X222 1 2 111X2 12 12 1X2 1X 反正让 2 走右边就行了。 2)现在 1 在第 y1 列,2 在第 y2 列,让 1 和 2 分别向右走,到达 yy1 和 yy2 列,然后向下 走一格。这样如果 yy1 < y2,便是分别取走第 y1~yy1,y2~yy2 列数,否则路线有重复,就取 走 y1~yy2 的数。 为了方便连续取数,我用了一个 sum[x,y1,y2]的数组,就是第 x 行的 y1~y2 的数。 由于递推是从 d[x1,y1,x2,y2]到 d[x1+1,y1',x2+1,y2'],而总有 x1=x2=x,所以可以把状

态节省为:d[y1,y2] 而把 x(当前行)作为阶段来递推: for x:=n-1 downto 1 do begin for y1:=1 to n do for y2:=y1 to n do 枚举 y1'和 y2'作为新的 y1 和 y2,注意保证 y1' >= y1, y2' >= y2(题目规定), y1' <= y2'(刚才的分析),递推 d[y1,y2] d1:=d2; {只记录相邻两个状态} end; 边界是什么呢?当然是从第 n 列的值了,就是 sum[n,y1,n](从 y1 取到 n) 一句话,就是两个人一起,一行一行往下走,每一行可以一次向右走若干步,但是要保 证 2 在 1 的右边。 注意最后输出的是 d2[1,1]。如果输出 d1[1,1],n=1 会得到 0。 参考程序: const maxn=10; var n:integer; m:array[1..maxn,1..maxn] of integer; d1,d2:array[1..maxn,1..maxn] of integer; sum:array[1..maxn,1..maxn,1..maxn] of integer; procedure init; var x,y,p:integer; i,j,k:integer; begin readln(n); fillchar(m,sizeof(m),0); repeat readln(x,y,p); if (x=0)and(y=0)and(p=0) then break; m[x,y]:=p; until false; {calc sum} for i:=1 to n do begin sum[i,1,1]:=m[i,1]; for j:=2 to n do

sum[i,1,j]:=sum[i,1,j-1]+m[i,j]; for j:=2 to n do for k:=j to n do sum[i,j,k]:=sum[i,1,k]-sum[i,1,j-1]; end; end; function max(a,b:integer):integer;begin if a>b then max:=a else max:=b; end; procedure solve; var y1,y2,yy1,yy2,x,r:integer; begin {init} for y1:=1 to n do for y2:=y1 to n do d2[y1,y2]:=sum[n,y1,n]; for x:=n-1 downto 1 do begin for y1:=1 to n do for y2:=y1 to n do begin d1[y1,y2]:=-maxint; for yy1:=y1 to n do for yy2:=max(y2,yy1) to n do begin if yy1>=y2 then r:=sum[x,y1,yy2]+d2[yy1,yy2] else r:=sum[x,y1,yy1]+sum[x,y2,yy2]+d2[yy1,yy2]; if r>d1[y1,y2] then d1[y1,y2]:=r; end; end; d2:=d1; end; end; begin init; solve; writeln(d2[1,1]); end. 2001 年 问题描述 给出一个长度不超过 200 的由小写英文字母组成的字母串(约定;该字串以每行 20 个字母 的方式输入,且保证每行一定为 20 个)。要求将此字母串分成 k 份(1<k<=40),且每份中包含 的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一 个字母不能再用。例如字符串 this 中可包含 this 和 is,选用 this 之后就不能包含 th)。 单词在给出的一个不超过 6 个单词的字典中。 要求输出最大的个数。 题三 统计单词个数

输入格式 去部输入数据放在文本文件 input3.dat 中,其格式如下: 第一行为一个正整数(0<n<=5)表示有 n 组测试数据 每组的第一行有二个正整数(p,k) p 表示字串的行数; k 表示分为 k 个部分。 接下来的 p 行,每行均有 20 个字符。 再接下来有一个正整数 s,表示字典中单词个数。(1<=s<=6) 接下来的 s 行,每行均有一个单词。 输出格式 结果输出至屏幕,每行一个整数,分别对应每组测试数据的相应结果。 样例 输入: 1 1 3 thisisabookyouareaoh 4 is a ok sab 输出: //说明:(不必输出) 7 // this/isabookyoua/reaoh 题目分析:略。 2003 年 题三 加分二叉树

【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,?,n) ,其中数字 1,2,3,?,n 为 节点编号。每个节点都有一个分数(均为正整数) ,记第 i 个节点的分数为 di,tree 及它的 每个子树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree 的左子树的加分× subtree 的右子树的加分+subtree 的根的分数 若某个子树为空,规定其加分为 1,叶子的加分就是叶节点本身的分数。不考虑它的空 子树。 试求一棵符合中序遍历为(1,2,3,?,n)且加分最高的二叉树 tree。要求输出; (1)tree 的最高加分 (2)tree 的前序遍历 【输入格式】 第 1 行:一个整数 n(n<30) ,为节点个数。 第 2 行:n 个用空格隔开的整数,为每个节点的分数(分数<100) 。 【输出格式】 第 1 行:一个整数,为最高加分(结果不会超过 4,000,000,000) 。 第 2 行:n 个用空格隔开的整数,为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】

145 3 1 2 4 5 题目分析: 很显然,本题适合用动态规划来解。用样例数据具体分析我们可以画出如下几种不同结 果的树: 4 3 2

2

5

1

4

1

4

1

3 图1

2 图2

5

3 图3

5

((5*1)+7)*10+2=122 显然输出结果是图2。

(7+5)*(10+2)+1=145

5*(1*10+2)+7=67

如果用数组 f[i,j]表示从节点 i 到节点 j 所组成的二叉树的最大加分,则动态方程可以 表示如下: f[i,j]= f[i,p-1]* f[p+1,j]+ f[p,p] 用数组 root[i,j]表示从节点 i 到节点 j 所组成的最大加分二叉树的根节点。 程序的关 键部分如下: For I:=1 to n do For j:=1 to n do begin r[i,j]:=0; f[i,j]:=1; end; For I:=1 to n do begin read(f[i,i]); r[i,i]:=i; end; For k:=1 to n-1 do For I:=1 to n-k do begin J:=I+k; For p:=I to j do If f[i,j]< f[i,p-1]* f[p+1,j]+ f[p,p] then Begin f[i,j]= f[i,p-1]* f[p+1,j]+ f[p,p]; r[i,j]:=p; end; 本题考查了二叉树的遍历和动态规划法。最大加分二叉树的前序遍历序列可能不唯一。 2004 年 合唱队形

<问题描述> N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱 队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2?,K,他们的身高 分别为T1,T2,?,TK, 则他们的身高满足T1<...<Ti>Ti+1>?>TK(1<=i<=K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同 学排成合唱队形。

输入文件 输入文件chorus.in的第一行是一个整数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。 题目分析: 动态规划。最基本的想法是:枚举中间最高的一个人,接着对它的左边求最长上升序列 (注意序列中最高的同学不应高过基准),对右边求最长下降序列(同样的,序列中最高的 同学不应高过基准)。 求最长上升(或下降)序列是经典的动态规划题我们都要掌握。本题只需要先求好最长 上升和下降序列,然后枚举中间最高的同学就可以了。 算法优化: 很明显可以看出,查询序列是单调的,于是可以用二分法,这个问题的算法效率就得到 了大幅度的提升,节省了时间。 程序已经不难写出。此处省略了。 本题不但体现了二分法的思想,而且也体现了多次动态规划的思想,这个思想在解决很 多问题的时候,都有很大的作用。 从往年的竞赛题中我们已经看到动态规划题几乎每年出现,而且每年奥赛题用动态规划 法都是综合应用,不是单一的一次动态规划。另外,编程一定要仔细分析题目,分析的一般 方法: 1、看清题意,分析可以用哪些算法;2、根据题意自己列举具体的具有一般性特点的 数据或样例数据分析题目,找出解题方法,再推广到一般的 n,并且要考虑各种情况(如特 殊的数据、边界等) ,最后到程序。


推荐相关:

4种常见的动态规划模型

(三)、区间类模型 区间类模型的动态规划, 一般是要求整段区间的最优值, 子问题一般是把区间分成两个 子区间。一般用二维数组表示状态,例如 f[i,j]表示从 i...


动态规划的技巧——阶段的划分和状态的表示

动态规划的技巧——阶段的划分和状态的表示在动态规划的设计过程中, 阶段的划分和状态的表示是非常重要的两步, 这两步会直接影响该问题的计算复杂性, 有时候阶段...


动态规划阶段总结之基础篇[必看]

动态规划阶段总结之基础篇 by Zc [序言]动态规划是信息学竞赛中最重要的知识点之一, 不仅思维难度高, 而且变化多端, 新思想新方法层出不穷, 要求选手具有很强...


动态规划习题

动态规划习题_理学_高等教育_教育专区。数学模型 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取值, 以使目标函数达到极大或极小。 在线 性规划和非...


动态规划与静态规划的关系

动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若 干约束条件下的函数极值问题。 两种规划在很多情况下原则上可以相互 ...


动态规划算法原理及应用

动态规划算法刘兴田(浙江工业大学 计算机学院 软件工程 1205 班 201226630512)摘要: 动态规划是解决最优化问题的基本方法,本文介绍了动态规划的基本思想 和基本步骤, ...


动态规划方法求解线性规划问题

动态规划方法求解下列线性规划问题。 max f ? 2x 1 ? 5x 2 ? x 3 ?2 x 1 ? x 2 ? 4 x 3 ? 10 ? ?x 1 , x 2 , x 3 ? 0 设 xi ...


运用动态规划模型解决最短路径问题

运用动态规划模型解决物流配送中的最短路径问题王嘉俊 (盐城师范学院数学科学学院 09(1)班) 摘要:随着现代社会的高速发展,物流配送成为了连接各个生产基地的枢纽,...


有关动态规划的一篇小论文

动态规划 Dynamic Programming by Starfish 【摘要】 本文介绍了动态规划的基本思想和基本步骤,通过实例研究了利用动态规划设计算 法的具体途径,讨论了动态规划的一些...


第4讲 动态规划

第4讲 动态规划_电脑基础知识_IT/计算机_专业资料。计算机算法设计与分析 第4讲 动态规划 我们先来看一个简单的多阶段决策问题。 现有一张地图,各结点代表城市,...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com