当前位置:首页 >> 学科竞赛 >>

动态规划


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

要 时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间;可以用一个表来记录 所有已解的子问题的答案;不管该子问题以后是否被用到,只要它被计算过,就将其结果填 入表中。具体的程序中一般用数组来记录子问题的答案。 二、动态规划问题的特征 适合采用动态程序设计方法的问题特征:最优子结构性质和子问题重叠性质。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,并且要考虑各种情况(如特 殊的数据、边界等) ,最后到程序。


相关文章:
动态规划(DP)的使用条件
,但从空间复杂度来看,动态规划算法为 O(n2),而搜索 算法为 O(n),搜索算法反而优于动态规划算法。选择动态规划算法是因 为动态规划算法在空间上可以承受,而搜索...
4种常见的动态规划模型
(三)、区间类模型 区间类模型的动态规划, 一般是要求整段区间的最优值, 子问题一般是把区间分成两个 子区间。一般用二维数组表示状态,例如 f[i,j]表示从 i...
动态规划讲解大全(含例题及答案)
2.动态规划问题中的术语 阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段 数就可能不同.描述阶段的变量称为阶段变量。在...
动态规划算法原理与应用
3.2 动态规划问题中的术语 阶段: 把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求 解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。...
动态规划算法举例分析
动态规划算法介绍 基本思想是将待求解问题分解成若干子问题,先求解子问题,最后用这些子 问题带到原问题, 与分治算法的不同是,经分解得到的子问题往往是不是相互...
动态规划理论(精华)
动态规划理论(精华)_IT/计算机_专业资料。动态规划理论一.动态规划的逆向思维法动态规划是一种思维方法,没有统一的、具体的模式。动态规划可以从多方面 去考察,不...
动态规划 分类
动态规划 分类_计算机软件及应用_IT/计算机_专业资料。动态规划分类 1、背包模型 包括 0-1 背包、无限背包、有限背包、有价值背包、小数背包(贪心即可) 等,是极...
动态规划基本原理
动态规划基本原理近年来, 涉及动态规划的各种竞赛题越来越多, 每一年的 NOI 几乎都至少有一道题目需 要用动态规划的方法来解决; 而竞赛对选手运用动态规划知识的...
动态规划及其在资源分配中的应用
动态规划及其在资源分配中的应用摘要:在概述动态规划原理的基础上,提出了动态规划的数学模型建模的主要步骤,将动态规划思 想运用到求解资源分配中,并通过一个实际...
2设计动态规划算法的主要步骤为
2设计动态规划算法的主要步骤为_数学_自然科学_专业资料。2 设计动态规划算法的主要步骤为: (1)找出最优解的性质,并刻划其结构特征。 (2) 递归地定义最优值。...
更多相关标签:
动态规划算法 | 动态规划原理及应用 | 动态规划 背包问题 | 贪心算法 | 动态规划算法例题 | 动态规划法 | 2038年问题 | 动态规划 最短路径 |