nbhkdz.com冰点文库

浙江省选一试讲课_图文

时间:2016-04-21

动态规划基础

——alpq654321

动态规划是用来干啥的
是用来做题目的。 ? 讲道理大家应该都听说过动态规划吧。
?

动态规划前的准备工作
求斐波那契数列。 ? 现有f[0]=f[1]=1,且f[i]=f[i-1]+f[i-2],求f[n]。
?

怎么做呢
根据题目意思,设计函数。 ? int f(int x) {return x<=1?1:f(x-1)+f(x-2);}
?

优化
然而用这种方法效率是极低的。大家不妨分析 一下复杂度。 ? O(n)=O(n-1)+O(n-2)。 ? 因此我们要计算f[n]时,它的时间复杂度也是 O(f[n])的。 ? 这里我们要引入一个记忆化搜索的概念。
?

记忆化搜索
? ? ? ? ? ? ? ?

我们发现对于一个值f(x)它一定不会改变。 但是我们在计算f(5)的过程中需要计算f(4)与f(3),而在计算f(4) 的过程中又需要计算f(3),这里f(3)就被计算了两次。 怎么优化呢。 为了避免这种重复运算。我们可以开一个数组fib来记录已经知 道的值。 即int f(x) {return fib[x]?fib[x]:fib[x]=f(x-1)+f(x-2);} 这里要注意在调用f数组之前我们就需要将fib[0]和fib[1]设初始 值1。 我们再来分析一下复杂度。 对于每个f(x),只会被f(x+1)与f(x+2)调用一次,这样就是线性啦!

另一种计算方法
在上述运算过程中,我们要知道f(x)的值需要 从前面调用。 ? 我们不妨从前往后计算f(x)。 ? 即f[x]=f[x-1]+f[x-2]。 ? 这样f[n]就是第n项斐波那契数列啦!
?

动态规划
在刚才的题目中,从某种意义上来说,虽然已 经有了阶段,但还不是真正的动态规划。 ? 动态规划的两个基本特征: ? 一、重叠子问题。 ? 二、最优子结构。 ? 然而在刚刚的题目中,仅仅只有重叠子问题, 我们可以称之为递推! ? 接下来我们来看一道较难的动态规划题。
?

吃金币游戏
?

在一个n*m的网格中,第i行第j列有ai,j(ai,j>0) 个金币。lyk要从(1,1)走到(n,m)且只能向右或 者下走,问它最多能收集多少金币。

吃金币游戏

我们来看如何用搜索来做出这个题目。 ? 令函数f(x,y)表示从(1,1)走到(x,y)最多能收集多少 金币。 ? 那么有 ? int f(int x,int y) ? {return min(x,y)==0?0:a[x][y]+max(f(x-1,y),f(x,y-1));} ? 其中min和max分别表示最小值和最大值。
?

记忆化搜索
?

?
? ? ? ? ? ? ? ? ? ?

然而我们发现这样子的搜索效率是极低的。 不妨来分析一下复杂度。 O(n,m)=O(n-1,m)+O(n,m-1)。 O(0,i)=O(i,0)=1。 实际上O(n,m)就相当于是从(1,1)走到(n,m)的路径条数,共 C(n+m-2,n-1)的复杂度。 那么如果我们使用记忆化搜索呢? 令dp[n][m]来记录从(1,1)走到(n,m)的最大值。 即有 int f(int x,int y) {return dp[x][y]?dp[x][y]:dp[x][y]=max(f(x-1,y),f(x,y-1))+a[x][y];} 注意边界。 这样就能使复杂度降低至O(nm)级别啦。

动态规划
我们不妨按顺序来做。 ? 即for (i=1; i<=n; i++) for (j=1; j<=m; j++) ? dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]; ? 这样就有一个最优子结构在里面啦! ? 这就是一个最简单的动态规划。
?

练习题1
给定一个长度为n的仅包含左括号或问号的字 符串,将问号变成左括号或右括号使得该括号 序列合法,求方案总数。 ? 例如(())与()()都是合法的括号序列。 ? n<=3000。
?

做动态规划题的一般步骤
先写出最简单的搜索。 ? 改成记忆化搜索。 ? 改变顺序变成循环的形式,写出动态规划的状 态和转移。 ? 就做完啦!
?

练习题1
? ? ?

?
? ? ?

考虑到大家都是来参加省选的,应该有相当高的水平。 我就直接略过前两个步骤啦! 令dp[i][j]表示当前到第i个字符,现在还有j个左括号。 那么分两种情况考虑。 若第i+1个字符是左括号,则能转移到dp[i+1][j+1]。 若第i+1个字符是问号,则能转移到dp[i+1][j-1]与 dp[i+1][j+1]。 最终dp[n][0]就是方案总数啦。 时间复杂度为O(n^2)。

优化
当n高达10W时怎么办呢? ? 状态可以通过滚动数组滚动掉一维。 ? 至今仍然还找不到一个理论时间复杂度能通过 时限的算法。 ? 不过可以通过卡常数,使得在不到4s内出解。
?

练习题2
给定n个由左右括号组成的字符串。选择其中 若干字符串,使得组成一个合法的括号序列且 长度最长。 ? n<=1000,Σ|si|<=10000。 ? 一个例子: ? ()、(()、) ? 答案是6,能组成(())()
?

练习题2
考虑一个合法括号序列的组成方案。 ? 一定不存在某个位置右括号个数大于左括号个 数的情况。 ? 每个括号序列可以形象地表示成3个参数。 ? 将其中合法的括号删除后,只有可能是左边若 干右括号,右边若干左括号,并记录其长度。
?

练习题2
?

? ? ?

我们将左括号个数大于等于右括号个数的提取出来, 表示加入该括号序列后,能增加左括号与右括号的差 值。 对于这些括号序列,将它们按照右括号个数从小到大 排序。因为右括号数量越少,越可能能够加入到末尾。 我们可以令dp[i]表示当前左括号个数-右括号个数=i时 的最大长度。 一个显然的转移是dp[i]=max{dp[i-(x[j]-y[j])]+len[j]}此时 还要满足y[j]<=i-(x[j]-y[j])。其中j表示当前枚举到第j个括 号序列,x[j],y[j],len[j]分别表示左右括号的个数与该括 号序列的长度。

练习题2
类似地,我们对左括号小于右括号的括号序列 提取出来。令dp2[i]表示当前右括号-左括号个 数=i的最大长度。 ? 这样我们只需要找到dp[i]+dp2[i]的最大值就是 答案了。 ? 时间复杂度为O(nΣ|s[i]|)。
?

练习题3
有一个栈,其中有n个数1~n按顺序依次进入 栈顶,在某个时刻弹出。 ? 其中m个限制,形如数字A必须在数字B之前弹 出。 ? 求方案总数,答案对大质数取模。 ? n<=300,m<=90000。
?

练习题3
考虑没有限制的情况。 ? 令dp[l][r]表示仅仅只有l~r这些数字进出栈的情 况。 ? 我们枚举最后出栈的数是x,那么有 dp[l][r]=Σdp[l][x-1]*dp[x+1][r]。 ? 其实就是卡特兰数列啦。
?

练习题3
?

?
? ? ? ? ? ?

考虑一个限制<A,B>,表示A必须在B之前弹出。 对于一个dp[l][r]若l<=A<=B<=r,则A不能作为最后一个 弹出,而其它都是可以的。 为什么呢? 当A<x<=B时显然成立。 当l<=x<A或B<x<=r时对于一边是没有影响的,对于另 一边在子dp中已经满足了A在B之前弹出。 若l<=B<=A<=r,则B+1~A不能作为最后一个出栈。若 这些成为最后出栈的数,则B显然会比A先被弹出。 枚举所有区间和x,判断是否可以转移。 那么我们就有了一个n^3m的做法。

优化
?

令v[i][j][k]表示在dp[i][j]中k是否可以作为转移。 ? 注意到在每个限制中,不能取的数一定是连续 的,因此我们对于每个限制可以枚举每个区间, 用并查集维护,时间复杂度降为n^2mα(n)。

继续优化
观察一个限制<A,B>,对于它来说,有用的区 间一定是l<=min(A,B)且r>=max(A,B)的,在二 维平面中,这本质上构成了一个矩形。 ? 因此我们只要枚举所有不合法的k,在这个矩 形中表示出来就可以了。 ? 表示的方法可以通过在4个端点中记录,dp的 时候判断前缀和是否大于0就行了。 ? 时间复杂度为n^3+nm。
?

练习题4
?

?
? ? ? ? ? ? ? ?

在一根数轴上有n个怪物,第i个怪物所在位置为ai。 其中有m个点时特殊点,第i个特殊点所在位置为bi。 若两个怪物相邻,则不能将它们拆开,可以认为是一个块。 可以有一个或者多个怪物是一个块。 每次可以将一个块的怪物向左移动或者向右移动直到撞到 怪物为止。 问最终最多有多少怪物能到达特殊点。 n<=100000,m<=2000。 5sec。 42 1845 72

练习题4
怪物与怪物之间顺序是不会变的。 ? 我们考虑前i个怪物最多能到达多少特殊点。 ? 对于第i个怪物,仅有两种可能。 ? 1:不动。 ? 2:向左移动。 ? 而向左移动的前提是开始时第i个怪物与第i+1 个怪物不在同一块。 ? 分这两种情况转移。
?

不动的情况
枚举一个特殊点,表示最终这个特殊点一定会 被怪物到达。 ? 假如这个特殊点所在位置是x,第i个怪物所在位 置为y,则相当于从第i-(y-x)个开始的怪物都得 向右移动,才能到达这个特殊点。其中第x~y 的特殊点都能被到达到。 ? 注意怪物形成一块的情况。
?

向左移动的情况
?

我们可以枚举特殊点,表示这个特殊点最终一 定会被到达,令x表示不超过该特殊点位置且 位置最大的怪物的位置,这个可以预处理出来。 ? 令y表示第i个怪物所在的位置。 ? 那么当满足x~y的怪物个数不小于x与该特殊点 距离时,便可以将这些点向左移动,转移即可。 ? 总复杂度为O(nm)。

练习题5
有两个栈分别有n和m个数。每次可以从其中 一个栈中取出一个数。令k表示不同的输出序 列总数,其中第i种输出序列产生方式有ai个。 求Σai^2,答案对一个数取模。 ? n,m<=500。
?

练习题5
?

?
? ?

? ? ?

非常经典的题目。 考虑ai^2所表示的意义。 即相同对的个数。 那么我们令dp[i][j][a][b]表示第一种方案在第一个栈取 了i个,第二个栈取了j个,第二种方案在第一个栈取了 a个第二个栈取了b个且输出序列相同的方案总数。 转移非常简单,枚举下一次两种方案分别在哪个栈取。 实际上i+j=a+b,因此只要3维就能表示状态了。转移 是O(1)的。 总复杂度为O(n^3)。

练习题6
一个游戏里有k种装备,每种装备初始等级为 1,每次打败一个怪兽,都会随机掉落一件一 种类型的装备,他的等级为[1,t+1]中随机一个 数x,其中t表示当时该类型的装备的等级。若 x=t+1,则换上掉落的装备,否则不换,然后 卖掉不用的装备,等级i的装备能卖i个金币, 求打败n个怪兽后的得到的金币的期望。 ? n<=100000,k<=100.
?

练习题6
?

?
? ? ?

?
? ? ? ?

根据期望的线性性,我们发现k并没有什么卵用。 可以拆分成k次子任务,即最终答案乘以k即可。 令dp[i][j]表示总共i次战斗,当前装备等级为j能获得的金币期望。 那么显然的有dp[0][j]=0。 对于dp[i][j],枚举下一个怪兽爆的装备等级,统计期望。 有dp[i][j]=1/k*Σ(x=1->j+1)1/(j+1)*(dp[i-1][max(j,x)]+min(j,x))+(k1)/k*dp[i-1][j]。 整理可得。 dp[i][j]=1/k*(j/(j+1)*(dp[i-1][j]+(j+1)/2)+1/(j+1)*(dp[i-1][j+1]+j))+(k1)/k*dp[i-1][j]。 注:此处的/均为除而不是整除。 这样状态就是O(n^2),转移就是O(1)啦!

继续优化
为了要得到一个等级为p的装备,就要在p-1的基础上 期望打上kp次。总共为2k+3k+...+pk≈p^2k次。那么 打败n只怪兽后,期望的装备等级为根号n/k级别的。 根据这个思路,我们可以推论,当状态dp[i][j]中j越大 增加的值越小。 事实上,当n=100000,k=1时,在j>700时只会产生非 常细微的变化。 因此我们可以将状态中的第二维的上界设成一个界限 B。 在保证精度的情况下,能较快的得到解,总复杂度为 O(nB)。

?

?
?

?
?

THANKS FOR WATCHING


浙江省选一试讲课_图文.ppt

浙江省选一试讲课_其它课程_高中教育_教育专区。动态规划基础 动态规划基础

浙江省选一试讲课素材_图文.ppt

浙江省选一试讲课素材 - 动态规划基础 alpq654321 动态规划是用来

...:选考试卷走向分析及教学启示 (共50张PPT)_图文.ppt

试试 3 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 ...怎么答 怎么教 探寻:教学操作 探问:命题依据 2017年4月浙江省政治选 考卷考...

2016年4月浙江省技术科通用技术学考选考试卷_图文.ppt

2016年4月浙江省技术科通用技术学考选考试卷_其它课程_高中教育_教育专区。2016...1/2 相关文档推荐 2016年4月浙江选考地理试... 9页 1下载券 2016年4月...

浙江省选考技术试卷绍兴模拟2019年3月_图文.pdf

浙江省选考科目考试绍兴市适应性试卷(2019 年 3 月) 6.某算法部分流程图

浙江省计算机等级考试讲座_图文.ppt

进入考 服务器端启动后,点击“进入考试系统” 试系统主界面; 试系统主界面; ...2010年春浙江省计算机等... 6页 1下载券 2013浙江省计算机等级考... 暂无...

2018浙江省高职考数学精讲_图文.ppt

试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 ...2018年浙江省单考单招数学(精讲)主讲人:岑佳威 1 考试时间:2018年6月中旬 ...

...- 浙江人事考试网 浙江省公务员 …_图文.ppt

试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 资格考试/认证...把拿到的土地一部 分租给浙江人种草莓。浙江人每亩地产草莓2500公斤,净赚5万 ...

浙江省编信息技术教材(1)_图文.ppt

浙江省编信息技术教材(1)_其它课程_小学教育_教育专区。文档均来自网络,如有.

浙江省2016年4月物理选考试卷_图文.pdf

黑,答案写在本试题卷上 准考证号用黑色字迹的签字笔或钢笔分别填写在试 标出...浙江2016年4月物理学考选... 暂无评价 9页 1下载券 浙江省2016年4月选...

热烈欢迎浙江省专家评估组莅临我校检查指导-PPT精选文....ppt

热烈欢迎浙江省专家评估组莅临我校检查指导-PPT精选...并要求教师给学生讲明为

浙江省普通高校招生选考科目考试模拟卷(冲刺版)地理(一....doc

浙江省普通高校招生选考科目考试模拟卷(冲刺版)地理(一) - 流过多少 汗,流

浙江省2018年选考加试题31题复习策略_图文.doc

浙江省2018年选考加试题31题复习策略_高考_高中教育_教育专区。注意事项:

《2016浙江省普通高中学业水平考试暨高考选考科目考试....ppt

《2016浙江省普通高中学业水平考试暨高考选考科目考试标准》解读 - 《2016年浙江省普通高中 学业水平考试 暨高考选考科目考试标准》 永康一中生物组:魏小鹏 第一...

2017年4月浙江地理选考加试题对地理教学的启示_图文.pdf

试试 1 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 ...2017 年 4 月浙江省地理选考加试题对地理教学的启示龙游县第二高级中学 戴...

2018年4月浙江省生物选考试题全部解析(李爽 陈婷婷 张伟健 戴利利....doc

(李爽 陈婷婷 张伟健 戴利利 李先明) (1)_理化...2018 年 4 月浙江省普通高校招生选考科目考试 生物...“检测生物组织中的蛋白质”需先加入双缩脲试 剂 ...

热欢迎浙江省专家评估组莅临我校检查指导_图文.ppt

热烈欢迎浙江省专家评估组 莅临我校检查指导 《浙江...并要求教师给学生讲明为什

浙江省严州中学2017届高三地理选考第一次模考试卷_图文.doc

浙江省严州中学(新)2017 届高三地理选考第一次模考试卷 命题人:洪明祥一、.

2017年11月浙江学考选考高中历史试[卷]和答案解析_图文.doc

WORD 完美格式 绝密★考试结束前 2017 年 11 月浙江省普通高校招生选

浙江省高职单考单招技能考试方案_图文.doc

浙江省高职单考单招技能考试方案 计算机类 一、指导思想 为贯彻执行教育部关于...必考模块 1+1 方式 程序设计技能 选考模块 计算机网络技术技能 数字媒体技术...