tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

历届动态规划题


题三

加分二叉树(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 [分析]很显然,本题适合用动态规划来解。如果用数组 value[i,j]表示从节点 i 到节点 j 所组成的二叉树的最大加分,则动态方程可以表示如下: value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j], value[i+2,i+2]+value[i,i+1]*value[i+3,j],?,value[j-1,j-1]+value[i,j-2]*value[j ,j], value[j,j]+value[i,j-1]} 题目还要求输出最大加分树的前序遍历序列,因此必须在计算过程中记下从节点 i 到节点 j 所组成的最大加分二叉树的根节点,用数组 root[i,j]表示 [PASCAL 源程序] {$N+} program NOIP2003_3_Tree; const maxn=30; var i,j,n,d:byte; a:array[1..maxn]of byte; value:array[1..maxn,1..maxn]of comp;

root:array[1..maxn,1..maxn]of byte; s,temp:comp; f1,f2:text;fn1,fn2,fileNo:string; procedure preorder(p1,p2:byte);{按前序遍历输出最大加分二叉树} begin if p2>=p1 then begin write(f2,root[p1,p2],' '); preorder(p1,root[p1,p2]-1); preorder(root[p1,p2]+1,p2); end; end; begin write('Input fileNo:');readln(fileNo); fn1:='tree.in'+fileNo;fn2:='tree.ou'+fileNo; assign(f1,fn1);reset(f1); assign(f2,fn2);rewrite(f2); readln(f1,n); for i:=1 to n do read(f1,a[i]); close(f1); fillchar(value,sizeof(value),0); for i:=1 to n do begin value[i,i]:=a[i];{计算单个节点构成的二叉树的加分} root[i,i]:=i;{记录单个节点构成的二叉树的根节点} end; for i:=1 to n-1 do begin value[i,i+1]:=a[i]+a[i+1];{计算相邻两个节点构成的二叉树的最大加分} root[i,i+1]:=i;{记录相邻两个节点构成的二叉树的根节点; 需要说明的是, 两个节 点构成的二叉树,其根节点可以是其中的任何一个;这里选编号小的为根节点,则编号大的 为其右子树;若选编号大的为根节点,则编号小的为其左子树;因此,最后输出的前序遍历 结果会有部分不同,但同样是正确的。如果最大加分二叉树的所有节点的度数都是 0 或 2, 则最后输出的前序遍历结果是唯一的。} end; for d:=2 to n-1 do begin{依次计算间距为 d 的两个节点构成的二叉树的最大加分} for i:=1 to n-d do begin s:=value[i,i]+value[i+1,i+d];{计算以 i 为根节点, i+1 至 i+d 间所有节点为 以 右子树的二叉树的最大加分} root[i,i+d]:=i; {记录根节点 i} for j:=1 to d do begin temp:=value[i+j,i+j]+value[i,i+j-1]*value[i+j+1,i+d];{计算以 i+j 为根 节点, i 至 i+j-1 间所有节点为左子树, i+j+1 至 i+d 间所有节点为右子树的二叉树的 以 以 最大加分} if temp>s then begin{如果此值为最大} s:=temp;root[i,i+d]:=i+j;{记下新的最大值和新的根节点} end;

end; temp:=value[i,i+d-1]+value[i+d,i+d];{计算以 i+d 为根节点,以 i 至 i+d-1 间 所有节点为左子树的二叉树的最大加分} if temp>s then begin s:=temp;root[i,i+d]:=i+d+1; end; value[i,i+d]:=s; end; end; writeln(f2,value[1,n]:0:0);{输出最大加分} preorder(1,n);{输出最大加分二叉树的前序遍历序列} close(f2); end. [点评]基本题。 考查了二叉树的遍历和动态规划算法。 难点在于要记录当前最大加分二叉树 的根节点。疑点是最大加分二叉树的前序遍历序列可能不唯一。

第三题:统计单词个数(2001)
给出一个长度不超过 200 的由小写英文字母组成的字符串(约定:该字符串以每行 20 个字母的方式输入,且保证每行一定 20 个) 。要求将此字符串分成 k 份(1<k≤40) ,且每 份中包含的单词个数加起来最大(每份中包含的单词可以重叠。当选用一个单词之后,其第 一个字母不能再用。 例如字符串 this 中可以包含 this 和 is, 但是选用 this 之后就不能再选 th) 。

分析:
这一题应该算是一道比较原创的题目。 注意到题目中有一个非常特殊的地方, 就是以串 中某个位置的字母为首字母,最多只能分出一个单词。由于在拆分字符串的过程中,如果以 某位置为首某个较短单词被截断, 那么以该位置为首的较长单词必然也会被截断。 也就是说, 对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。 这样我们 可以定义一个在位置 i 的参数 m le n [ i ] 表示以位置 i 的字母为首字母, 所能形成的最短单词的 长度。 这样如果在这个位置加上这个单词的长度之内截断, 则以该位置为首字母就不能形成 1 2 单词,否则就可能形成一个单词 。这样对于所有的不同 l 个首位置,我们只要在各个位置 依次对各个单词进行匹配就以得出所对应的 m len 的值,这一部分的复杂度为 O(wl2)3。然 后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分, 故我们类比其他的分割字串的问题,列出动态规划的方程如下:

1 2 3

当然前提是在这个位置可以匹配上一个单词。 这里 l 为该字串的长度。 这里 w 为单词的个数。

f [ l , k ] ? m ax

1? i ? l ?1

? f [l ? i, k

? 1] ? g [ l ? i ? 1, i ]?

这里有初值 f [ l ,1] 为:
f [ l ,1] ? g [1, l ]

这个式子中, f [ l , k ] 表示把字串前 l 个字符分成 k 段时所形成的最多单词的数目,
g [ p , i ] 表示字串的第 p 个字符开始的 i 个字符形成的字串中所能形成的单词数。这里 g [ p , i ] 由于过于庞大,不能用预计算的方法加快速度,只能现用现算。计算的方法为对于

所有 p ? q ? p ? i ? 1 的 q ,如果 m len [ q ] 存在(也就是有单词可以在位置 q 匹配上) ,且
q ? m len [ q ] ? 1 ? p ? i ? 1 ,则该位置必然可以匹配上一个单词。把所有这样位置的数目加

起来就可以得到 g [ p , i ] 的值了。这样算法的复杂度为 O(kl3)。 但这里计算还有一个技巧, 就是我们可以依次按照 k 增加,l 增加,i 增加的顺序计算 f 的值。这样在 i 由 i ' 增加到 i '? 1 的时候,由于在计算 i '? 1 所对应的 g 值时可以用
g [ p ? 1, i ' ? 1] ? g [ p , i '] ? 1 ? g [ p , i '] p ? 1 ? m le n [ p ? 1] ? 1 ? p ? i ' ? 1 p ? 1 ? m le n [ p ? 1] ? 1 ? p ? i ' ? 1

这个方程进行复杂度为 O(1)的递推计算,故总复杂度可以降到 O(kl2+wl2)。 这种被称作双重动态规划的方法,请读者自己好好体会。

数据:
输入 21 thisisappleisthisthe oopbooktheisurrtoywe 4 is of the book 44 dfhfghgdfksgdflsdsds sdsdsddfsdffssddsfdf asasassasdsdsdsdsdsd 输出

1

8

2

13

sadadadasdsdsdsdssdd 4 dssd dfdfdf sdsd jkjjk 10 4 aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa 1 aaaaa 10 4 sdfsdsassdasdddsasdd sdasdsasdsadasdasdsa assasaasadassadsaadd ssasdasdasdssddsassa asdasdasdasdasddsads dsadasdasdasadssdssa asssdasdsasdassdssaa dsaddsasdasdsadsaasa adsadsasddsadsadsssa adsdsaasddsaadsdsasa 6 aa sa ds da sa sd 10 4 sdfsdsassdasdddsasdd sdasddassdsaadaasdsa assasaasadassadsaadd ssasdsaasdassddsassa saddssassasdsaasssds dsasdasdsddasdasdssa

3

193

4

125

5

65

asssdasdsasdassdssaa sadsassdssassdsasssa sasdsasdsasdsasdsssa sdsasdsasdsassdasdsa 6 asd dsa ads das sad sda

(2000)
题二 乘积最大 (22 分) 问题描述: 今年是国际数学联盟确定的“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

第二题: 很明显的动态规划。 令 d[i,j,k]为第 i 个数字到第 j 个数字加 k 个乘号所能够达到的最大值。 状态转移方程是: d[i,j,k]=max{num[i,t]*d[t+1,j,k-1]} (枚举 t, 满足 i<=t<=j-1) 注意到状态转移的时候总是使 k 减小 (或不变) 所以把 k 作为阶段来递推 的, (节 约空间)。 在每个状态中,l=j-i 越来越小,所以从 l=0 递推到 l=n 即: for k:=1 to c do for l:=0 to n do for i:=1 to n do 递推 d[i,j,k] 显然,用两个数组记录 d[i,j,k]和 d[i,j,k-1],就可以只用两维:d[i,j] 于是算法框架就是(请对照我的源程序): 初始化 d1[i,j] for k:=1 to c do begin for l:=0 to n do for i:=1 to n do 用 d1[i,j](k-1 阶段)递推 d2[i,j](k 阶段) d1:=d2; {节省空间,因为递推的时候只与上个阶段有关,故只保留相邻两个 阶段} end; 高精度乘法的方法我不是用的模拟手算的过程(这个大家会做吧),而用了类似 多项式乘法的方法, 因为我觉得这种写法很好记! (大家仔细看看我的 mul 过程) 程序见附件。

题四 方格取数 (33 分) 问题描述: 设有 N*N 的方格图(N<=8), 我们将其中的某些方格中填入正整数, 而其他的方格中则放人数字 0。 如下图所示(见样例 ,黄色和蓝色分别为两次走的路线,其中绿色的格子为黄色和蓝色共同走 过的): A 13 7 14 21 15 14 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 4 6

第四题:

有同学搜索第一个人,拣了以后第二个人用动态规划,一定能得最优解,但时间 效率不大高。 有同学采用贪心, 即用动态规划算出第一个人最大能拣的数,再在剩下的数中用 动态规划。 反例如下: 1 9 1 0 0 0 1 9 1 第一次是: 1->9->9->1 第二次是:1 和是 21 但显然可以两次把所有的数拣完(22)。 本题是典型的多维动态规划,很象 IOI93 的第四题,另一个算法是网络流,很象 IOI97 第一题, 这里我只分析前者。这道题目的简单之处是阶段很好划分(对角线),这种方法 我就不介绍了, 因为很多地方都有介绍。这里讲一种怪一点的动态规划^_^ 容易想到的思路是: 令 d[x1,y1,x2,y2]表示甲在 x1,y1,乙在 x2,y2 以后(包括取走(x1,y1))的过程 中可以获得的最大和。 则 d[1,1,1,1]就是原问题的解。 但是是否能取数和另一个人是否事先已经到过该格子有关, 我们需要设计一种走 的方法,使得只根据 x1,y1, x2,y2 就能判断一些关键的格子是否已经到达过。这样,问题才具有无后效性。 为此,我们把路线作如下处理: 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) 说了这么多,真不知道我说清楚了没有( 好象是没有:-P ),如果有什么不明 确的地方,请大家在论坛上提出来。 一句话,就是两个人一起,一行一行往下走,每一行可以一次向右走若干步,但 是要保证 2 在 1 的右边。 注意最后输出的是 d2[1,1]。如果输出 d1[1,1],n=1 会得到 0。(为什么?自己 想啊) 现在程序就不难写了吧。程序见附件: 测试数据见附件。

第一题 拦截导弹(28 分)(1999) 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦 截系统 有一个缺陷: 虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都 不能高 于前一发的高度。 某天, 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段, 所以 只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整 数),计算 这套系统最多能拦截多少导弹, 和如果要拦截所有导弹最少要配备多少套这种导 弹拦截 系统。 样例: INPUT 389 207 155 300 299 170 158 65 OUTPUT 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系统数)

[分析] 有经验的选手一看第一个问就知道是经典的动态规划 - 最长不升子序列。 令 d[k]为打中第 k 枚导弹以后,含第 k 枚导弹在内一共最多可以打 k 枚,则有状 态转移方程: d[k]= MAX {d[i]+1,1} (i>k)and(d[i]<=d[k]) 显然有 d[n]=1,故从 n 逆推至 d[1]即可,则 MAX{d[k]}为所求。 1<=k<=n 第二问显然要难一点,最直观的算法是贪心,但是反例也容易找到,如: 6 5 1 7 3 2 如果第一次打 6 5 3 2,显然还要打两次,而最好的方案是 6 5 1/7 3 2。 显然失败之处在于第一种方案为了多打 3 和 2,把 1 和 7 隔断了, 但事实上把 3 和 2 留给第二套打 还不是一样! 因为每个导弹都要打到,故我们应该把注意力放在“打到每一枚导 弹”。 在上一个例子中,7 是必须打到的, 因为它是最高的,所以必有一次拦截是以 7 开头的!!!

既然是必须,那么打 7 的同时顺便打一打其他的绝对不比不打差!那么打哪些 呢? 下面说明:应该打后面导弹中最高的一个 K。 先定义一个概念:把当前能打的最大高度叫做“能力” 理由如下: 对于 K 以后的导弹,绝对该打 K,因为对于 K 以后的导弹,不打 K 时能打到的, 打了 K 也能打到(K 是最高的嘛!), K 等于是“白打”,而对于 7 和 K 之间的导弹,打了任何一个就一定不能再打 K 了(K 最高嘛!)反正中间的和 K 不能一次打,先打不会比后打差! 类似的,下一个目标是 K 后面的最高的。 可以证明,该算法是正确的(从略),基础较好的同学也可以通过建立有向无环 图来理解和证明这一算法。 程序见附件。


推荐相关:

中科院计算机算法_陈玉福_历年试题

中科院计算机算法_陈玉福_历年试题_计算机软件及应用_IT/计算机_专业资料。中国科学...动态规划算法利用子问题重叠性质,对每一个子问题只计算一次,将其解保存在一个...


上海大学历年运筹学考研真题及答案、考研大纲

3、 分枝定界法在需要分枝时必须满足:一是分枝后的各子问题必须容易求解;二是各子问 题解的集合必须覆盖原问题的解。 4、 在动态规划基本方程中,凡子问题具有...


历年全国数学建模试题及解法

.历年全国数学建模试题及解法 赛题 解法 93A 非线性交调的频率设计 拟合、规划 93B 足球队排名 图论、层次分析、整数规划 94A 逢山开路 图论、插值、动态规划 ...


历年NOIP试题难度列表

历年NOIP试题难度列表_学科竞赛_高中教育_教育专区。历年 NOIP(普及组)难度分析...动态规划 或 贪心 字符串处理 数学 或 枚举 动态规划 回溯 动态规划 数学(...


历年国家集训队论文题目

历年国家集训队论文题目_法律资料_人文社科_专业资料。1999 年陈宏 - 数据结构的...灵活运用——动态规划的深入探讨 齐鑫 - 搜索方法中的剪枝优化 邵铮 - 数学...


动态规划习题详解

动态规划习题详解_文学_高等教育_教育专区。动态规划习题 动态规划动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化问题的一种方法. 动态规划是运筹学的一...


动态规划习题

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


基本动态规划问题的扩展(国家集训队 俞玮)

基本动态规划问题的扩展(国家集训队 俞玮)_军事/政治_人文社科_专业资料。ACM基本...事实上,这一题的 w 有其特殊的性质: 对于 a≤ b≤ c≤ d,我们有 w(a...


动规习题

动规习题_IT/计算机_专业资料。动规习题 DP1 邮局问题(post) 一些村庄建在一...动态规划习题详解 32页 2下载券 tyvj第四届月赛题解 6页 2下载券©...


几个经典的动态规划问题

几个经典的动态规划问题_计算机软件及应用_IT/计算机_专业资料。经典动态规划动态...2015国考行测模拟试题历年真题 2015国考申论押密试卷及答案 2015国考面试通关...

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