《浙江省选一试讲课素材课件》由会员分享，可在线阅读，更多相关《浙江省选一试讲课素材课件（37页珍藏版）》请在金锄头文库上搜索。
1、是用来做题目的。讲道理大家应该都听说过动态规划吧。求斐波那契数列。现有f0=f1=1,且fi=fi-1+fi-2,求fn。根据题目意思，设计函数。int f(int x) return x0)个金币。lyk要从(1,1)走到(n,m)且只能向右或者下走，问它最多能收集多少金币。我们来看如何用搜索来做出这个题目。令函数f(x,y)表示从(1,1)走到(x,y)最多能收集多少金币。那么有int f(int x,int y) return min(x,y)=0?0:axy+max(f(x-1,y),f(x,y-1);其中min和max分别表示最小值和最大值。然而我们发现这样子的搜索效率是极低的。不妨
2、来分析一下复杂度。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)的复杂度。那么如果我们使用记忆化搜索呢？令dpnm来记录从(1,1)走到(n,m)的最大值。即有int f(int x,int y)return dpxy?dpxy:dpxy=max(f(x-1,y),f(x,y-1)+axy;注意边界。这样就能使复杂度降低至O(nm)级别啦。我们不妨按顺序来做。即for (i=1; i=n; i+) for (j=1; j=m; j+) dpij=max(dpi-1j,
3、dpij-1)+aij;这样就有一个最优子结构在里面啦！这就是一个最简单的动态规划。给定一个长度为n的仅包含左括号或问号的字符串，将问号变成左括号或右括号使得该括号序列合法，求方案总数。例如()与()()都是合法的括号序列。n=3000。先写出最简单的搜索。改成记忆化搜索。改变顺序变成循环的形式，写出动态规划的状态和转移。就做完啦！考虑到大家都是来参加省选的，应该有相当高的水平。我就直接略过前两个步骤啦！令dpij表示当前到第i个字符，现在还有j个左括号。那么分两种情况考虑。若第i+1个字符是左括号，则能转移到dpi+1j+1。若第i+1个字符是问号，则能转移到dpi+1j-1与dpi+1j+
4、1。最终dpn0就是方案总数啦。时间复杂度为O(n2)。当n高达10W时怎么办呢？状态可以通过滚动数组滚动掉一维。至今仍然还找不到一个理论时间复杂度能通过时限的算法。不过可以通过卡常数，使得在不到4s内出解。给定n个由左右括号组成的字符串。选择其中若干字符串，使得组成一个合法的括号序列且长度最长。n=1000，|si|=10000。一个例子：()、()、)答案是6，能组成()()考虑一个合法括号序列的组成方案。一定不存在某个位置右括号个数大于左括号个数的情况。每个括号序列可以形象地表示成3个参数。将其中合法的括号删除后，只有可能是左边若干右括号，右边若干左括号，并记录其长度。我们将左括号个数大
5、于等于右括号个数的提取出来，表示加入该括号序列后，能增加左括号与右括号的差值。对于这些括号序列，将它们按照右括号个数从小到大排序。因为右括号数量越少，越可能能够加入到末尾。我们可以令dpi表示当前左括号个数-右括号个数=i时的最大长度。一个显然的转移是dpi=maxdpi-(xj-yj)+lenj此时还要满足yj=i-(xj-yj)。其中j表示当前枚举到第j个括号序列，xj,yj,lenj分别表示左右括号的个数与该括号序列的长度。类似地，我们对左括号小于右括号的括号序列提取出来。令dp2i表示当前右括号-左括号个数=i的最大长度。这样我们只需要找到dpi+dp2i的最大值就是答案了。时间复杂度
6、为O(n|si|)。有一个栈，其中有n个数1n按顺序依次进入栈顶，在某个时刻弹出。其中m个限制，形如数字A必须在数字B之前弹出。求方案总数，答案对大质数取模。n=300,m=90000。考虑没有限制的情况。令dplr表示仅仅只有lr这些数字进出栈的情况。我们枚举最后出栈的数是x，那么有dplr=dplx-1*dpx+1r。其实就是卡特兰数列啦。考虑一个限制，表示A必须在B之前弹出。对于一个dplr若l=A=B=r，则A不能作为最后一个弹出，而其它都是可以的。为什么呢？当Ax=B时显然成立。当l=xA或Bx=r时对于一边是没有影响的，对于另一边在子dp中已经满足了A在B之前弹出。若l=B=A=r
7、，则B+1A不能作为最后一个出栈。若这些成为最后出栈的数，则B显然会比A先被弹出。枚举所有区间和x，判断是否可以转移。那么我们就有了一个n3m的做法。令vijk表示在dpij中k是否可以作为转移。注意到在每个限制中，不能取的数一定是连续的，因此我们对于每个限制可以枚举每个区间，用并查集维护，时间复杂度降为n2m(n)。观察一个限制，对于它来说，有用的区间一定是l=max(A,B)的，在二维平面中，这本质上构成了一个矩形。因此我们只要枚举所有不合法的k，在这个矩形中表示出来就可以了。表示的方法可以通过在4个端点中记录，dp的时候判断前缀和是否大于0就行了。时间复杂度为n3+nm。在一根数轴上有n
8、个怪物，第i个怪物所在位置为ai。其中有m个点时特殊点，第i个特殊点所在位置为bi。若两个怪物相邻，则不能将它们拆开，可以认为是一个块。可以有一个或者多个怪物是一个块。每次可以将一个块的怪物向左移动或者向右移动直到撞到怪物为止。问最终最多有多少怪物能到达特殊点。n=100000,m=2000。5sec。4 21 8 4 57 2怪物与怪物之间顺序是不会变的。我们考虑前i个怪物最多能到达多少特殊点。对于第i个怪物，仅有两种可能。1：不动。2：向左移动。而向左移动的前提是开始时第i个怪物与第i+1个怪物不在同一块。分这两种情况转移。枚举一个特殊点，表示最终这个特殊点一定会被怪物到达。假如这个特殊点
9、所在位置是x,第i个怪物所在位置为y，则相当于从第i-(y-x)个开始的怪物都得向右移动，才能到达这个特殊点。其中第xy的特殊点都能被到达到。注意怪物形成一块的情况。我们可以枚举特殊点，表示这个特殊点最终一定会被到达，令x表示不超过该特殊点位置且位置最大的怪物的位置，这个可以预处理出来。令y表示第i个怪物所在的位置。那么当满足xy的怪物个数不小于x与该特殊点距离时，便可以将这些点向左移动，转移即可。总复杂度为O(nm)。有两个栈分别有n和m个数。每次可以从其中一个栈中取出一个数。令k表示不同的输出序列总数，其中第i种输出序列产生方式有ai个。求ai2，答案对一个数取模。n,m=500。非常经典
10、的题目。考虑ai2所表示的意义。即相同对的个数。那么我们令dpijab表示第一种方案在第一个栈取了i个，第二个栈取了j个，第二种方案在第一个栈取了a个第二个栈取了b个且输出序列相同的方案总数。转移非常简单，枚举下一次两种方案分别在哪个栈取。实际上i+j=a+b，因此只要3维就能表示状态了。转移是O(1)的。总复杂度为O(n3)。一个游戏里有k种装备，每种装备初始等级为1，每次打败一个怪兽，都会随机掉落一件一种类型的装备，他的等级为1,t+1中随机一个数x，其中t表示当时该类型的装备的等级。若x=t+1，则换上掉落的装备，否则不换，然后卖掉不用的装备，等级i的装备能卖i个金币，求打败n个怪兽后的
11、得到的金币的期望。n=100000,kj+1)1/(j+1)*(dpi-1max(j,x)+min(j,x)+(k-1)/k*dpi-1j。整理可得。dpij=1/k*(j/(j+1)*(dpi-1j+(j+1)/2)+1/(j+1)*(dpi-1j+1+j)+(k-1)/k*dpi-1j。注：此处的/均为除而不是整除。这样状态就是O(n2)，转移就是O(1)啦！为了要得到一个等级为p的装备，就要在p-1的基础上期望打上kp次。总共为2k+3k+.+pkp2k次。那么打败n只怪兽后，期望的装备等级为根号n/k级别的。根据这个思路，我们可以推论，当状态dpij中j越大增加的值越小。事实上，当n=100000,k=1时，在j700时只会产生非常细微的变化。因此我们可以将状态中的第二维的上界设成一个界限B。在保证精度的情况下，能较快的得到解，总复杂度为O(nB)。Gl & hf人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。
