提高组——动态规划

《提高组——动态规划》由会员分享，可在线阅读，更多相关《提高组——动态规划（40页珍藏版）》请在装配图网上搜索。

1、动态规划题目选动态规划题目选刘汝佳例1. ProbabilisticTranslator 你要翻译一篇文章, 每个原文单词都有若干候选翻译词汇. 要求翻译后相邻单词的权和尽量大. 例如 原文是a b c 翻译选项为: a : x y; b: y z; c: x y 权为w(y,z)=20, w(x,y)=10, w(z,x)=5 则翻译成x y z权和为10+20=30 原文最多50个单词. 最多50个单词对权非0分析 令f(k,t)为前k个单词的翻译结果中, 其中最后一个单词采取第t种翻译, 得到的最大权和例2. RPSChamps n(n=500)个人进行剪刀石头布游戏, 每次每人等概率的

2、出剪刀石头或者布, 直到一共只出现两种(否则重来一次,计入局数), 然后分别在内部继续. 两部分的局数都计入总局数. 求游戏总局数的期望分析 先计算某一局内a人出石头b人出剪刀的概率P(a,b)=(P(a-1,b)+P(a,b-1)/3 则一局不重来的概率为Pn=sum3P(i,n-i) 设fn为所求, 则fn=(1-Pn)*(1+fn)+sum3P(i,n-i)*(1+fi+fn-i) 移项得到递推公式例3. Collector 你想收集所有硬币. 最少需要取多少钱, 使得不管取款机怎么给钱都可以得到所有种类硬币? 例如1,2和1,1都是无解的. 但2,3的解是5, 因为只有一种方案5=2+

3、3 最多50种硬币, 每个硬币面值为1到10000分析 何时无解? 存在倍数的情况? 不一定. 例如3,5,8. 无解当且仅当有两种不同的方式得到所有硬币面值和sum. f(i,j)表示用前i种硬币得到j的方法总数例3. 旅行计划 某人沿高速公路旅行，白天行走，晚上在旅馆住宿，每天最多走800公里。旅行社给出了沿路旅馆的相关信息，包括离出发点的距离和该旅馆的价格. 任意两个旅馆之间的距离都将在800公里以内. 求出住宿费用最少的旅行计划 冲突:日程最短住宿次数最少的旅行计划 冲突: 费用最少分析 设di为到旅馆i的最少费用，则有di=mindj+costi，ji, dist(j,i)=800

4、算法一算法一: 直接计算, 时间O(n2). 如果可以快速计算一段连续区间的最小值, 则时间复杂度将得到降低! 算法二算法二: 用滑动窗口技术，用堆保存满足满足dist(j,i)=L=800的状态的状态dj，每个元素最多删除和增加一次，共O(nlogL)分析 对窗口内的点, 如果有idj则可以只保留dj, 因为因为dj更好且更好且i能取时能取时j一定也能取一定也能取 在新加入结点时从右往左查找, 找到位置前把结点删除, 直到找到正确的位置 每个点最多加入和删除一次，因此为O(n)例4. 基因 字符串变换规则A1A2A3, 其中A1, A2, A3各为一个大写字母,表示字母A1可以被替换为串A2

5、A3. 给定串, 判断它是否可以由字母S经过若干次替换生成.分析 逆向思维：Ai,j,c为真当且仅当ij-1的子串可以合成字母c。 递推时可枚举k，对于规则A1A2A3 如果Ai,k,A2且Ak,j,A3 ，则Ai,j,A1 即Ai,j,A1 |= Ai,k,A2 & Ak,j,A3 状态有26L2个，转移有262L个，总263L3。 Bi,j为ij的子串最少可以合成几个S，O(n2) 特殊处理：用整数表示c1c2能直接合成的集合ec1,c2，用位运算加速例5. n-k special sets 我们说一个由自然数构成的集合X是n-k特殊集合，如果它满足 对于集合X中的每个元素x，有1=x=n

6、， 集合X中所有元素的和大于k 集合X中不包含任意一对相邻的自然数 给出n, k，求n-k特殊集合有多少个分析 di,j为i-j特殊集的个数，则分两类 不包含i的，为di-1,j 包含i的，为di-2,j-i 注意边界 滚动数组例6. Lecture Halls Reservation 有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。 分析 按照结束时间从小到大排序 di = maxdj + Leni，其中j

7、为右端点在i左端点前的线段集合。显然该集合是连续的若干个线段 用堆维护dj，O(nlogn)。由于需要排序，这是下界。如果已经按右端点排序好，则需要二分找到可用线段的最右端，再插入状态例7. 氧气瓶 用(a,b,c)描述一个氧气瓶，其中a表示氧气体积，b为氮气体积，c为重量 带多个氧气瓶，则三者都相加 给出n种氧气瓶，选择其中的一些，使得氧气至少T升，氮气至少A升，重量最轻分析 Di,j,k为只考虑前i个氧气瓶，需要氧气至少j升，氮气至少为k升的最小重量。 时间复杂度：O(n*T*A)例8. CoolNumbers 如果一个数的二进制表达式(不含前导0)中至少有三个连续0或者三个连续1, 我们

8、称它为cool number. 例如8=(1000)2, 15=(1111)2都是cool number, 但27=(11011)2不是 求a到b中的cool number个数. 例如0到16有5个cool number: 7, 8, 14, 15, 16; 17到100有49个. 0=a=b=2147483647分析 记f(x)为0到x的cool number个数, 则答案为f(b)-f(a-1) 集合分解: 0,1011010)的数分为以下几部分: 0* 100* 1010* 101100* 问题转化为求已知前缀的串个数分析 如果肯定cool了, 则直接得到结果 否则只需要考虑最后的连续数

9、字. 设f(i,j,k)为包含i位且最后有j个连续的k(k=0,1)时的cool number个数, 递推即可例9. Code 给定包含前K个字母的BST，代码为：空树(包含零个字母)的代码为空串. 否则第一个字母为根，接着是左子树代码，最后是右子树代码 代码排序，第n个代码记为(n,k)-代码 目标：给定n, k，找到(n,K)-代码。（n,K为正整数，1=K=19）例9. Code 当k=4时有14个4结点BST。它们是（按字母表顺序）：abcd，abdc，acbd，adbc，adcb，bacd，badc，cabd，cbad，dabc，dacb，dbac，dcab，dcba 字母串badc

10、是(7,4)-代码，如右图分析 题目中讲的二叉树就是排序二叉树，而BST代码，实际上就是二叉树的先序遍历。题目中所要求的，就是把所有的有k个结点的排序二叉树排序的BST代码排序后（按字典顺序），排在第n位的代码。 总数： fi=sumfj-1*fi-j 计算以j为根的BST总数Xj=fj-1*fk-j，则把n与X1比较后直接可算出根。同样也可以算出左儿子和右儿子例10. 划分 把一个集合分成k份, 使得它们的方差和尽量小. 方差等于所有数与平均数差的平方的平均数. 例如3,4,7,10的平均值为6, 则方差为(3-6)2+(4-6)2+(7-6)2+(10-6)2)/4=7.5 最多50个数,

11、 每个数为1到1000的整数 例如1000,500,1,500分成三份, 方差和最小为0. 1000, 500,500, 1分析 最优解一定是排序后分成若干段 f(i,j)表示从i开始的数分成j段的最小方差和, 则f(i,k)=minf(j,k-1) + var(i,j) | ij=n, 其中var(i,j)表示第i到j-1个数的方差. 时间复杂度为O(n2k)例11. 阶梯 有一些高度递增的阶梯, 每次可你可以 如果下个阶梯比当前阶梯高1个单位, 可以直接到该阶梯 如果不是在第一个阶梯, 都可退到前一个阶梯 如果你已经连续退了K次, 则可以到达比当前阶梯最多高2K个单位的任何一个阶梯 用最少

12、移动数到最后一个阶梯,或输出无解 最多50个阶梯, h1=0, 0=hi=109分析 设f(i)为到达第i个台阶的最小次数, 考虑这之前到达的最高台阶, 即经过若干次后退后直接可达第i个台阶.C0 = 0; for(i=1;in;i+) Ci = 1000000; if (hi - hi-1 = 1) Ci = Ci-1+1; for(j=0;ji;j+) for(k=0;kj;k+) if (hiCj+j-k+1)Ci=Cj+j-k+1; if (Ci = 1000000) return -1; return Cn-1; 例12. ExtendedHappyNumbers Sk(N)表示N的

13、各位数的k次方之和. 例如S2(65)=62+52=61. 则N的happy值定义为不停计算Sk(N), Sk(Sk(N)过程中得到的最小值. 给定A, B, K, 计算A到B的每个数的happy值之和. 例如k=2时5得到的序列为5,25,29,85,89,145,42,20,4,16,37,58,89, 1=A=B=106, K=6分析 可以到达的最大数不超过4*106, 因为36+6*96=31893754*106 用Hash判断重复, 记f(n)为n的happy值, 则每个f(n)最多算一次.例13. PrefixFreeSubsets 如果一个字符串集合中没有某个串是另一个的前缀,

14、称该集合为PrefixFree的. 给一个字符串集合, 统计它的子集中PrefixFree的个数. 例如“hello”, “hell”, “hi”中除“hello”,”hell”和“hello”,”hell”,”hi”外的其他6个子集均为PrefixFree的. 最多50个串, 串长不超过50, 串由小写字母组成分析 算法一算法一: 建立Trie, 把单词结点做标记. 设f(i)为以i为根的子树中选择单词组成的PrefixFree集合的方案数, 则它等于所有儿子的f值乘积. 如果i本身是单词, 则加1 算法二算法二: 排序后i为根所在子树在序列中是连续的, 且i在最前面. 令d(i)为从i及其

15、后面的单词中选出PrefixFree集合的方案总数, 则d(i)=d(i+1)+d(j), 其中j为第一个不以wi为前缀的单词例14. 酸雨 你是一个农夫, 有一个一维农场. 你有一些保护庄稼的档板. 每个档板用三元组(b,e,y) 表示它是一条线段(b,y)-(e,y). 设所有b的最小值为B, 所有e的最大值为E. 买总长度尽量短的档板保护开区间(B,E)的所有庄稼. 酸雨落到档板后往最近的端点流. 如果落到档板中间则分成两半分别往两个端点流. 有公共端点的档板相当于一块大档板 最多25个档板, 0=be=10, 1=y=105分析 F(X,Y)表示只允许买高度不超过Y的档板, 挡住从集合

16、X处下落的雨水所需要的最少档板数,则f(empty,Y)=0, 且f(X,0)=infinity, 对于非空集X 离散化Y, 时间复杂度为22E-1*maxy例15. 植树 在w*h的网格的整点里种n棵树, 要求共线且相邻树的距离不小于d. 下图为w=h=10, n=4, d=2时的两种方案(还有其他方案). 求方案数 1=n,d=50, 1=w,h=500例16. NiceOrUgly 如果一个串包含3个连续元音或者5个连续辅音, 称它是ugly的, 否则nice. 给出包含大写字母与问号?的串, 返回它是否一定为UGLY, 一定为NICE或者不一定 AEIOU为元音, 其他为辅音 H?LO

17、WOR?是NICE的, EE?FFFF为UGLY的, HELLOW?RLD不一定(填O是nice, Z是ugly), 最多50个字符例17. Triple-Free Sets 求1,2,n满足条件的子集个数: 若x在集合中则2x和3x都不在.f(10)=198, f(20)=43776. n=100,000分析 每一个数看做一个节点，在所有的x与2x之间连一条边，所有的x与3x之间也连一条边，求这个图中独立集的个数即可 不同的连通块之间是互不影响的，只需要不同的连通块之间是互不影响的，只需要分别求解，最后乘起来即可。分别求解，最后乘起来即可。 把所有的数分解成若干个连通块分别处理。而每个连通块

18、都有如下形式：x2i3j（其中x是一个与2*3互质的数）。 图的形态 看成网格, 一共log3N列, 按行dp 记忆化, 最大数是x2i3j的不同x本质相同5*21*30=105*22*30=205*20*30=55*20*31=155*21*31=30例18. 排队买饭 N个菜排成一排, m个人前来排队. 每个人拿一种菜的时间是10秒. 每10秒种每个人尽量往前走(直到走不动或者到了自己想要的菜前). 注意即使拿完了所有菜也要排队出去. 移动时间忽略不计. 每个菜前恰好站一个人,只能拿自己面前的菜 中途不能插队也不能往回走 设计排队顺序让最后一个人尽早拿完菜. 最多8个菜,各不相同, 最多12个人, 每个人给出想拿的菜集合. 多解输出字典序最小