《清北学堂2012国庆noip课件——动态规划》由会员分享，可在线阅读，更多相关《清北学堂2012国庆noip课件——动态规划（60页珍藏版）》请在金锄头文库上搜索。
1、动态规划贾志豪清北学堂十一NOIP培训班动态规划的分类 线性动态规划 树型动态规划 状态压缩动态规划 与图论结合线性动态规划一维、二维、多维Transmission Delay 给定一个长度为n的01串，作为机器的输入 （n 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 你可以在任意位置插入一个数（数
2、值可以为0到255之间的任意值），花费为I 你可以改变一个数的值，花费为新数值与旧数值之差的绝对值 现在你的任务是在花费尽量少的情况下使得改变化的序列任意相邻两个数之差的绝对值小于M N =B fij=fi+1j else交换兔子问题 方法2： 从后开始往前计算，分别计算出每一个兔子按照他的 初始速度是否可以到达x=B， Ablei=1 iff Xi+T*Vi=B 设ci等于i之后不可以按时到达x=B的兔子个数Ural实验 在ural大学的一个教授的别墅上有一鹰巢。教授对这个鹰巢 很感兴趣。经过仔细观察，他发现鹰巢中有若干枚蛋。于是 他想利用这些蛋做一个试验。测试一下蛋的坚固程度。 这些蛋应该
3、是具有相同的坚硬度。存在一个非负整数E，如 果从楼的第E层往下扔蛋，但不会破，但如果从第E1层（ 包括高于E1层）扔，蛋就会破。你要做一组试验，来找出 E。最简单的方法是一层层试。但是你有多个蛋是，不必用 笨方法，可以用更少的次数找出E。注意这里的次数都是指 对你的方法的最坏情况且蛋破了就不能再用，还有E可以取0 。 如果实验到了最高层蛋还不破，则认为E取最高层的层数。鹰蛋实验 数组fi,j表示用i个鹰蛋需要试验j层，在最坏情况下最小 值 若在k层实验，如何确定最坏情况？ 如果碎了。则用剩下i-1个鹰蛋实验k-1层，即fi-1,k-1 如果没碎。则用这i个鹰蛋实验j-k层，即fi,j-k串的计
4、数 一个长度为3N字符串满足：由N个A，N个B，N个C组 成，对于它的任意前缀，满足A的个数=B的个数=C 的个数。求满足这样条件的字符串的个数。 N =j=k fijk+=fij-1k if i=j=k, j-1=k fijk+=fijk-1 if i=j=k树形动态规划二叉树染色 你的任务是要对一棵二叉树的节点进行染色。每个节点 可以被染成红色、绿色或蓝色。并且，一个节点与其子 节点的颜色必须不同，如果该节点有两个子节点，那么 这两个子节点的颜色也必须不相同。给定一棵二叉树的 二叉树序列，请求出这棵树中最多和最少有多少个点能 够被染成绿色。二叉树染色 fig表示根节点为i的子树，如果根染绿
5、色，最多有多 少个点能染绿色 fin表示根节点为i的子树，如果根不染绿色，最多有 多少个点能染绿色 fig=flchin+frchin+1fin=maxflchin+frchig,flchig+frchin布尔树 本题我们考虑一个完全二叉树 每一个叶子节点对应一个值，为0或者1 每一个中间节点对应一个符号，为AND或者OR 一些内部节点可以改变，即AND运算变成OR运算或者 OR变成AND 现在希望让你改变尽可能少的节点使得根节点的输出值 为V(0或者1) 节点个数0 x到v有节点 如果考虑回路的话，fstartvstate表示Salesman从 start出发，当前再v节点，已经走过的节点状
6、态为staten车问题 在n*n(n20)的方格棋盘上放置n 个车，某些格子不能 放，求使它们不能互相攻击的方案总数。n车问题 distate表示填完前i行放完之后，前i行占摆的列状态 为state时的方案总数 distate = sumdi-1state-2x (i,x)可以放 state 1= Q_i = V; P_i != Q_i)，轨道有一个开心值F_i (0 = F_i = 2,000,000,000)，Bessie总 的开心值就是经过的所有轨道的开心值之和。 Bessie自然希望越开 心越好，并且，她有足够长的时间在轨道上玩。因此，她精心地挑选 路线。但是，由于她是头奶牛，所以，会
7、有至多K (1 = K = 10)次的 情况，她无法控制，并且随机从某个水池选择了一条轨道(这种情况甚 至会在1号水池发生)如果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为节点编号。每个节点都有一个分数（
8、均为 正整数），记第j个节点的分数为di，tree及它的每个子树都 有一个加分，任一棵子树subtree（也包含tree本身）的加分 计算方法如下： subtree的左子树的加分 subtree的右子树的加分subtree 的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点 本身的分数。不考虑它的空子树。 n= 30加分二叉树 树形动归 Fij表示编号从i到j的节点组建的树的最大的分？ 计算顺序？架设电话线最近，Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话 服务，于是，她们要求FJ把那些老旧的电话线换成性能更好的新 电话线。新的电话线架设在已有的N(2 = N
9、= 100,000)根电话线 杆上，第i根电话线杆的高度为height_i米(1 = height_i = 100)。 电话线总是从一根电话线杆的顶端被引到相邻的那根的顶端，如 果这两根电话线杆的高度不同，那么FJ就必须为此支付C*电话线 杆高度差(1 = C = 100)的费用。当然，你不能移动电话线杆， 只能按原有的顺序在相邻杆间架设电话线。Farmer John认为，加高某些电话线杆能减少架设电话线的总花费 ，尽管这项工作也需要支出一定的费用。更准确地，如果他把一 根电话线杆加高X米的话，他得为此付出X2的费用。请你帮 Farmer John计算一下，如果合理地进行这两种工作，他最少要在 这个电话线改造工程上花多少钱。架设电话线 Hi为第i个电线杆的原始高度 Fih表示将第i个电线杆高度改为H的最小花费 Fih = min(Hi-h)2 + Fi-1h + C*|h-h| (h为变元) O(N*H2) 优化状态转移 lown,h = minlown,h-1, f(n,h)+C*h highn,h = minhighn,h+1, f(n,h) - C*h Fi,h=(Hi-h)2+min-C*h+lown-1,h+C*h+highn-1,h
