清北学堂2012国庆NOIP课件——动态规划

1、动态规划贾志豪清北学堂十一NOIP培训班动态规划的分类 线性动态规划 树型动态规划 状态压缩动态规划 与图论结合线性动态规划一维、二维、多维Transmission Delay 给定一个长度为n的01串，作为机器的输入 （n = 2000） 机器的输出保证：是一个长度为n的01串0的个数于输入相同每一个0、1有可能被delay第i位输入有可能是输出的第j位，满足|i-j|=D 编写程序计算共有多少个可能的输出计算可能的输出中，字典序第k个是多少USACO 2009 Holiday delayTransmission Delay Dij表示如果输出串前i位已经确定了，并且有j个0的情况下，有多少

2、种可能的输出串 DNK = 1 Dij += Di+1j+1 iff |jA| & |pos0j-i|=D Dij += Di+1j iff |i-jB| & |pos1i-j-i|=D家谱个数 农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 = N 200)。这些二叉树有如下性质: 每一个节点的度是0或2。度是这个节点的孩子的数目。 树的高度等于K(1 K 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。 有多少不同的家谱结构? 如果一个家谱的树

3、结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。http:/ tableij表示深度为i，包含j个节点的tree的个数 smalltreesij表示深度小于等于i，包含j个节点的tree的个数 tableij += smalltreesi-2k*tablei-1j-1-k; tableij += tablei-1k*smalltreesi-2j-1-k; tableij += tablei-1k*tablei-1j-1-k; smalltreesij = smalltreesi-1j + tableij最大矩形问题（1） 给定一个M行N列的图，图中的一

4、些格子是坏的，请找出最大的正方形矩阵，其中不包含任何一个坏格子。最大矩形问题（2） 如果把正方形换成等腰直角三角形，应该怎么做？最大矩形问题（3） 如果把正方形换成直角菱形，应该怎么做？最大矩形问题（4） 给定一个M行N列的图，图中的一些格子是坏的，请找出最大的长方形矩阵，其中不包含任何一个坏格子。最大矩形问题 给定一个M*N的网格，每个格子可以是黑或白色。 现在要求你按照如下方式从M*N的网格中剪出围棋棋盘：围棋棋盘必须为黑白相间正方形棋盘，每次从棋盘中剪出可能的最大棋盘，如果有多个的话选择最上方的一个，如果还有多个的话选择最左边的一个，直到把M*N的网格剪完为止（最后你要cut out所有

5、1*1的棋盘）。 输入每一个大小的棋盘各剪出了多少个。 N, M = 512http:/ 用部分和技术计算larg 时间复杂度 O(N*M) 把larg值全部存到Heap中，用Heap来维护最大值 如何更新larg数组？ 删除的正方形左边的和上边的点不用更新 所以，如果删除了一个k*k的正方形，我们只需要更新2k*2k范围的larg数组 所以update的时间复杂度是O(N*M)Crisis 一个无限大的地图上有一些士兵和一些旗子 司令员可以下达四种口令：分别让所有士兵向东、西、南、北前进一个单位 如果执行完一个指令后，有K个士兵到达了有旗子的位置，那么司令员可以得到K分 问司令员在最多下达C

6、个指令的情况下，最多能得到几分 数据规模士兵数量=1000，旗子数量=1000指令数量 C =30USACO 2008 Open crisisCrisis 所有士兵的相对位置不变，只有每个士兵距自己初始点的相对位置有意义 设Dijk表示执行完i个指令、每个士兵距离自己的初始点相对位置为(j,k)的情况下，司令的最大的分 Dijk = 第i个指令的得分+max Dij+/-1k+/-1香樟树被誉为江南四大名木之一的香樟树很有特色，它的树皮粗糙，质地却很均匀，从来没有白杨树的斑斑驳驳、没有柳树的肿瘤结节；树枝树干一分为二、二分为四一路长去，不会偷工减料也不会画蛇添足；树冠的形态是球形的，在天空中画

7、出优美的曲线。除了上述优点之外，香樟树还有一个秘密武器。那就是它凭借朴实、厚重的优秀品格赢得了小狐狸的青睐！话说有一天，小狐狸正在湖边散步，忽然一阵风吹来，她赶紧闭上眼睛。当她再次睁开眼睛时，发现美丽的湖畔多出了一排整齐的香樟树。小狐狸非常兴奋，她对每棵树都观察入微，并且数出了它们的叶子个数。她觉得如果相邻两棵树的叶子个数互素是不和谐的。因此小狐狸想从一排香樟树中选出若干棵，在满足相邻两棵树的叶子个数不互素的条件下，使得树尽量多。 对于60%的数据n=1000对于100%的数据 n=100000，叶子个数=100000 http:/ 假设n个数为a1an nave做法：di表示以第i个数结尾的

8、最长子序列di = maxdj+1 | j 1复杂度O(n2) 基于素数分解的做法：dij表示只使用前i个数，最后一个数包含素数pjdij = di-1k+1 | if ai%pj=0, ai%pk=0dij = di-1j | if ai%pj!=0Make it smooth 你有一列N个数字，每一个数字都在0到255之间； 你可以删除一个数，它左右两个邻居变为新的邻居，花费为D 你可以在任意位置插入一个数（数值可以为0到255之间的任意值），花费为I 你可以改变一个数的值，花费为新数值与旧数值之差的绝对值 现在你的任务是在花费尽量少的情况下使得改变化的序列任意相邻两个数之差的绝对值小于M

9、 N =B fij=fi+1j else交换兔子问题 方法2： 从后开始往前计算，分别计算出每一个兔子按照他的初始速度是否可以到达x=B， Ablei=1 iff Xi+T*Vi=B 设ci等于i之后不可以按时到达x=B的兔子个数KNiicicAnserUral实验 在ural大学的一个教授的别墅上有一鹰巢。教授对这个鹰巢很感兴趣。经过仔细观察，他发现鹰巢中有若干枚蛋。于是他想利用这些蛋做一个试验。测试一下蛋的坚固程度。 这些蛋应该是具有相同的坚硬度。存在一个非负整数E，如果从楼的第E层往下扔蛋，但不会破，但如果从第E1层（包括高于E1层）扔，蛋就会破。你要做一组试验，来找出E。最简单的方法是

10、一层层试。但是你有多个蛋是，不必用笨方法，可以用更少的次数找出E。注意这里的次数都是指对你的方法的最坏情况且蛋破了就不能再用，还有E可以取0。 如果实验到了最高层蛋还不破，则认为E取最高层的层数。鹰蛋实验鹰蛋实验 数组fi,j表示用i个鹰蛋需要试验j层，在最坏情况下最小值 若在k层实验，如何确定最坏情况？ 如果碎了。则用剩下i-1个鹰蛋实验k-1层，即fi-1,k-1 如果没碎。则用这i个鹰蛋实验j-k层，即fi,j-k1, 1 1, 1maxmin,1kjifkifjifjk串的计数 一个长度为3N字符串满足：由N个A，N个B，N个C组成，对于它的任意前缀，满足A的个数=B的个数=C的个数。

11、求满足这样条件的字符串的个数。 N =j=k fijk+=fij-1k if i=j=k, j-1=k fijk+=fijk-1 if i=j=k树形动态规划二叉树染色 你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。二叉树染色 fig表示根节点为i的子树，如果根染绿色，最多有多少个点能染绿色 fin表示根节点为i的子树，如果根不染绿色，最多有多少个点能染绿色 fig=flchin+frch

12、in+1fin=maxflchin+frchig,flchig+frchin布尔树 本题我们考虑一个完全二叉树 每一个叶子节点对应一个值，为0或者1 每一个中间节点对应一个符号，为AND或者OR 一些内部节点可以改变，即AND运算变成OR运算或者OR变成AND 现在希望让你改变尽可能少的节点使得根节点的输出值为V(0或者1) 节点个数=10000http:/ F(v, x)表示如果想让以v为根的子树的结果为x(0或者1)，最少需要改变多少个gate 状态转移比较复杂，这里举一个例子（考虑中间节点本来为OR） F(v, 0)=min F(u, 0) + F(w, 0), 1 + F(u, 0),

13、 1 + F(w, 0) 世界杯2010 有2P只球队进入世界杯淘汰赛，每一场比赛都有一个门票价格； 主人公最多只能错过Mi场第i只球队的比赛，问至少要花多少钱买门票 P = 10http:/ M=1 2 3 2 1 0 1 3世界杯2010 可以把上图当成一个树结构，每一场比赛当成一个节点 每一个节点可以取或不去，但要满足一些约束(最少看多少场) fvi表示以v为根的子树，如果v到根的路径上(不包括v)已经看了i场比赛时，v子树的最小花费 fvi = 不要v的时候，flchvi+frchvi 要v的时候，flchvi+1+frchvi+1+costv没有上司的晚会 有个公司要举行一场晚会。为

14、了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司都可以邀请。已知每个人最多有唯一的一个上司。 已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。 没有上司的晚会 在多叉树上进行动态规划，转移的时候需要使用01背包的技术 技巧：多叉树变二叉树，计算孩子的时候考虑父亲的状态 fv0表示在二叉树表示中，v的父亲不去参加舞会的情况下，以v为根节点的子树能获得的最大值 fv1为v的父亲参加的情况下 fv0=maxflchv0, flchv1+valv+frchv0 fv

15、1=flchv0+frchv1奶牛大集会Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1=N=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 = A_i =N; 1 = B_i = N),长度为L_i(1 = L_i = 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住者C_i(0 = C_i = 1,000)只奶牛。在选择集会的地点的时候，Bessie希

16、望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。http:/ 经典题型，两次DFS解决 第一次DFS的时候，计算每一个点v的所有孩子节点到v的距离和 第二次DFS的时候，计算所有节点到点v的距离和奶牛大集会状态压缩动态规划A Funny Stone Game David 玩一个石子游戏。游戏中，有n堆石子,被编号为0.n-1。两名玩家轮流取石子。每一轮游戏，每名玩家选取3堆石子i,j,k(ij

17、,j=k,且至少有一枚石子在第i堆石子中)，从i中取出一枚石子，并向j，k中各放入一枚石子(如果j=k则向k中放入2颗石子)。最先不能取石子的人输。 请编程帮助David。 石子堆的个数不会超过23，每一堆石子不超过1000个。A Funny Stone Game 每一堆的个数是没有意义的，有意义的是奇偶性 考虑j=k的情况，也就是向k中放入2颗石子 是不是等价于不向k中放石子？ 状态压缩动态规划TSP 一个n个点的带权的有向图，求一条路径，使得这条路经过每个点恰好一次，并且路径上边的权值和最小（或者最大）。或者求一条具有这样性质的回路。 n 0 x到v有节点 如果考虑回路的话，fstartv

18、state表示Salesman从start出发，当前再v节点，已经走过的节点状态为staten车问题 在n*n(n20)的方格棋盘上放置n 个车，某些格子不能放，求使它们不能互相攻击的方案总数。n车问题 distate表示填完前i行放完之后，前i行占摆的列状态为state时的方案总数 distate = sumdi-1state-2x (i,x)可以放 state&2x0n车问题 小拓展：如果所有格子都可以放的话-n! 如果放的是皇后而不是车的话K-排列问题 考虑一个1n的排列a1,a2,a3an，若max(abs(ai-i)=K，那么这个排列就称为K-排列。 求n个数的K-排列的个数

19、。 范围：n=100, K=5K-排列问题 前i个填完之后，哪些数可能用过也可能没用过： i+1-k i+k共2k个 所以我们动态规划的时候只要保存这些数字的状态就好了 distate表示填完前i个数，i+1-ki+k的使用情况是state的时候，有多少种填法 distate=sumdi-1trans(i, state, x)炮兵阵地（NOI2001） 在N*M网格地图上部署炮兵部队。每个炮兵可以控制横纵2格范围。任意一对炮兵互相不能处于控制范围。 地图上有些点不能部署部队。 N = 100；M = 10。 炮兵阵地 状态压缩dp，只考虑一行的状态行不行？ dpistate1state2表示考

20、虑前i行摆炮兵，第i行摆的状态是state1，第i-1行摆的状态是state2的情况下，最多能摆多少个炮兵 发现很多状态不合法，可以考虑用搜索来优化时间复杂度。与图论有关的动态规划冲浪受到秘鲁的马丘比丘的新式水上乐园的启发，Farmer John决定也为奶牛们建一个水上乐园。当然，它最大的亮点就是新奇巨大的水上冲浪。超级轨道包含 E (1 = E =150,000)条小轨道连接着V (V = 50,000)个水池，编号为1.V。每个小轨道必须按照特定的方向运行，不能够反向运行。奶牛们从1号水池出发，经过若干条小轨道，最终到达V号水池。每个水池(除了V号和1号之外，都有至少一条小轨道进来和一条小

21、轨道出去，并且，一头奶牛从任何一个水池到达V号水池。最后，由于这是一个冲浪，从任何一个水池出发都不可能回到这个水池)。每条小轨道从水池P_i到水池Q_i (1 = P_i = V; 1= Q_i = V; P_i != Q_i)，轨道有一个开心值F_i (0 = F_i = 2,000,000,000)，Bessie总的开心值就是经过的所有轨道的开心值之和。 Bessie自然希望越开心越好，并且，她有足够长的时间在轨道上玩。因此，她精心地挑选路线。但是，由于她是头奶牛，所以，会有至多K (1 = K = 10)次的情况，她无法控制，并且随机从某个水池选择了一条轨道(这种情况甚至会在1号水池发生

22、)如果Bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？http:/ 第二题冲浪 dxk表示Bessie从x出发前往V，中间最多可能“悲剧”k次的情况下，最坏情况下的开心值 dxk=min 不受控制mindyk-1+valxy 受控制maxdyk+valxyBackup Slides加分二叉树加分二叉树 设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分 subtree的右子树的加分subtree的根的分