动态规划讲解课件

历届NOIp动态规划讲解,动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划算法把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，以得到全局最优策略。 动态规划是信息学竞赛中选手必须熟练掌握的一种算法,它以其多元性广受出题者的喜爱。近年来，动态规划几乎每次都出现在NOIp的赛场上，而且还有越来越多的趋势。因此，掌握基本的NOIp动态规划题是至关重要的。,动态规划实质：,枚举,+,递推,状态,状态转移方程,Sample Problem1,1,3,5,9,1,从树的根到树的叶节点，最多能取多少数？,贪心：答案错误,暴力搜索：如果数据大会超时,动态规划！,我们先将NOIp里的动态规划分分类：,最长不降子序列 背包 方格取数 石子归并 状态压缩 数学递推 顺序递推,最长不降子序列,设有由n个不相同的整数组成的数列，记为: a(1)、a(2)、a(n)且a(i)a(j) (i，j=n) 例如3，18，7，14，10，12，23，41，16，24。 若存在i1i2i3 ie 且有a(i1)a(i2) a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。最长的不下降序列就是求长度最长的子序列。 For i:=1 To n Do For j:=1 To i-1 Do If (ai=aj)And(fifj+1) Then fi:=fj+1;,合唱队形（NOIp2004） 【问题描述】 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK， 则他们的身高满足T1Ti+1TK(1=i=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入文件】 输入文件第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高。 【输出文件】 输出文件包括一行，这一行只包含一个整数，就是最少需要几位同学出列。,Sample Problem2,最长不降子序列,最长不降子序列,最长不降子序列,最长不降子序列,依此类推,最长不降子序列,拦截导弹（NOIp1999） 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数）,Sample Problem3,最长不降子序列,第一问：最长下降子序列。,第二问：DP？,反例： 9 8 7 1 10 6 5 4,最长不降子序列,9 8 7 1 10 6 5 4,DP：,9 8 7 1 10 6 5 4,1 10,1 10,10,10,3次！,最长不降子序列,9 8 7 1 10 6 5 4,贪心：,2次！,9 8 7 1 10 6 5 4,10 6 5 4,DP不是万能的！,10 6 5 4,背包,01背包：有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。求解将哪些物品装入背包可使价值总和最大。 完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 For i:=1 To n Do For j:=Max Downto ai Do (ai To Max) If fjfj-ai+bi Then fj:=fj-ai+bi;,背包,Sample Problem4,金明的预算方案（NOIp2006） 【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为： vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。,背包,Sample Problem4,【输入文件】 第1行，为两个正整数N m（其中N（0，表示该物品为附件，q是所属主件的编号） 【输出文件】 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。【输入样例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200,背包,For i:=1 To n Do For j:=m Downto ai Do If fj-ai-1 then Begin 00 If fj-ai+bifj Then fj:=fj-ai+bi; Ff:=fj-ai+bi; 01 If j+si,1,1fj+si,1,1 Then fj+si,1,1:=Ff+si,1,2; 10 If j+si,2,1fj+si,2,1 Then fj+si,2,1:=Ff+si,2,2; 11 If j+si,1,1+si,2,1fj+si,1,1+si,2,1 Then fj+si,1,1+si,2,1:=Ff+si,1,2+si,2,2; End; End;,背包,Sample Problem5,邮票面值设计（NOIp1999） 给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1MAX之间的每一个邮资值都能得到。 例如，N=3，K=2，如果面值分别为1分、4分，则在1分6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。 【样例】 INPUT N=3 K=2 OUTPUT 1 3 MAX=7,背包,如果你一看到这道题目就想到搜索，那么,恭喜你，你答对了！,方格取数,Sample Problem6,方格取数 （NOIp2000） 设有N*N的方格图(N=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。,方格取数,13+14+4+21+15=67,方格取数,一取方格数：fi,j:=maxfi-1,j,fi,j-1; 现在要做的数二取方格数，是否还能像一取方格数那样如法炮制呢？,答案是肯定的！,我们观察一下它的路径。fi,j是从fi-1,j或者fi,j-1走来。无论是从fi-1,j还是fi,j-1走来，要么是x坐标+1，要么是y坐标+1，总归x坐标的值+y坐标的值一定比前一个多1。 我们来验证一下：,方格取数,X坐标（3，3） 3+3=6 Y坐标（3，4） 3+4=7 Z坐标（4，4） 4+4=8,方格取数,再观察，我们发现，走第n步时，能走到点是固定的。观察其坐标我们发现，第n步能走到的点其坐标和为n-1。,因此，走到第n步时，x坐标和y坐标的和就知道=n+1，这样我们就不必同时知道2条路线x坐标和y坐标了，知道其中一个t，另外一个就可以用n+1-t来表示了。,于是此题迎刃而解！,方格取数,用fx,i,j表示走到第x步时，第1条路线走到横坐标为i的地方，第2条路线走到了横坐标为j的地方。这样，我们只要枚举x，i，j，就能递推出来了。,For x:=3 To m+n Do For i:=1 To Min(x,n) Do For j:=1 To Min(x,n) Do Begin fx,i,j:=Max(fx-1,i,j,fx-1,i-1,j,fx-1,i,j-1,fx-1,i-1,j-1); If i=j Then Inc(fx,i,j,ai,x-i) Else Begin Inc(fx,i,j,ax-i,i); Inc(fx,i,j,ax-j,j); End; End;,同样三取方格数只要fx,i,j,k用同样的方法即可。,方格取数,传纸条（NOIp2008） 【问题描述】 小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高 的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学 的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。,Sample Problem7,石子归并,Sample Problem8,石子归并原题 【题目描述】 在一个圆形操场的四周摆放着N堆石子(N= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(=20). 选择一种合并石子的方案,使用权得做N1次合并,得分的总和最小。 【输入数据】 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔。 【输出数据】 一行，最小总和。 【输入】 4 4 5 9 4 【输出】 22,石子归并,4,5,9,4,石子归并,我们用fi,j表示以i堆石子为开头，以j堆石子为结尾的一系列石子归并起来的最小总和。 因为题目中说，只能归并相邻的两堆石子。所以，fi,j这一系列石子必然由fi,k和fk+1,j（i=kj）这两堆石子归并而来。只要在所有的fi,k+fk+1,j中取个最小值（就是原来此次没归并前的最小值），加上自己本身所有石子的和（因为归并一次的代价是所有石子的总和），就是我们要求的fi,j。 因此，状态转移方程为：,而fi,i和一段石子的总和是可以预处理的，只要将石子序列倍长，复杂度O(n3)，此题就能顺利AC了。,石子归并,For i:=1 To n-1 Do For j:=1 To 2*n-i Do Begin fj,j+i:=Maxlongint; For k:=j To j+i Do If fj,j+ifj,k+fk+1,j+i Then fj,j+i:=fj,k+fk+1,j+i; fj,j+i:=fj,j+i+Sumj,j+i; End; 这样，求归并的最大值也是同样的方法，不再赘述。,石子归并,Sample Problem9,能量项链（NOIp2006） 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。 需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为(41)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 (41)2)3）=10*2*3+10*3*5+10*5*10=710。,石子归并,Sample Problem10,乘积最大（NOIp2000） 【问题描述】 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 【输入】 程序的输入共有两行： 第一行共有2个自然数N，K（6N40，1K6） 第二行是一个长度为N的数字串。 【输出】 输出所求得的最大乘积（一个自然数）。 【样例输入】 4 2 1231 【样例输出】 62,石子归并,这道题目要求把一个长度为n的数字串分成k段，使得每段的乘积最大。 通过刚才的石子归并思想，我们可以用fi,j表示前i个数字我分了j段所能得到的最大值，那么fi,j就可以从fk,j-1（前k个数字分成了j-1段）推来，因为fi,j就是fk,j-1和（k+1i）这段数字串的乘积。 于是状态转移方程即可得出： fi,j:=Maxfk,j-1*Numberk+1,i (j-1=ki) 其中Numberk+1,j表示数字串从第k+1位到第i位转换成数字的值。 对于题目中所说的具有很强枚举意味的变量（如k段，n次等），一般将其放入状态中枚举。而诸如最大值最小值之类的变量，一般放入数组中作为值递推。,Sample Problem11,统计单词个数（NOIp2001） 【问题描述】 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串 以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分 成k份(1k=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。 例如字符串this中可包含this和is，选用this之后就不能包含th)。单词在给出 的一个不超过6个单词的字典中。要求输出最大的个数。 【样例输入】 3 thisisabookyouareaoh 4 is a ok sab 【样例输出】 7 this / isabookyoua / reaoh,石子归并,石子归并,看到这道题目应该马上有这种意识了：和乘积最大神似！ 所以本题除了求出ij之间有多少单词以外基本上就没什么难度了。预处理出ij之间有多少单词，其实也可以用DP。 首先，题目告诉我们，如果a是b的前缀，那么b肯定没用了（为什么）。所以第一步删串。之后的任务就是求单词数了。令si,j表示ij之间有多少个单词，那么si,j=si,j-1+以第j位为结尾，包含在ij这段串里的单词个数。 如串cabce，单词有cab、abc。明显第13之间有1个单词，而14之间呢？13有的它肯定也有，再去枚举单词中有没有是cabc后缀的单词。最终f1,4=f1,3+1。,Sample Problem12,矩阵取数游戏（NOIp2007） 【问题描述】 帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下： 1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素； 2. 每次取走的各个元素只能是该元素所在行的行首或行尾； 3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）； 4. 游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写个程序，对于任意矩阵，可以求出取数后的最大得分。 【输入】 第一行为两个用空格隔开的整数n和m。 第2n+1行为n*m矩阵，其中每行有m个用单个空格隔开 【输出】 一个整数，即输入矩阵取数后的最大的分。 【限制】 60%的数据满足：1=n, m=30，答案不超过106 100%的数据满足：1=n, m=80，0=aij=1000,石子归并,改变一下题目的叙述：每行有m个数，倒数第i次取的得分是ai*2(m+1-i)；倒推，因为每次只能取一段中的头或尾，所以剩下的永远是连续的一段，每次加入头或尾。 把一段的头和尾看做一堆石子，把ai*2(m+1-i)看做每次归并的加分，每次归并不是取相邻的，而是取一段中的头或尾就是石子归并。 用fi,j,k表示第i行，取了一些数后剩下连续的一段从j到k，那么状态转移方程就很好写了： fi,j,k:=Maxfi,j-1,k+aj-1*2(m-k+j-1) fi,j,k+1+ak+1*2(m-k+j-1); 这道题目还要高精度，建议写好非高精的DP再修 改成高精度的。,石子归并,状态压缩,过河（NOIp2005） 【问题描述】 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 【输入文件】 第一行一个正整数L（1 = L = 109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 = S = T = 10，1 = M = 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 【输出文件】 一个整数，表示青蛙过河最少需要踩到的石子数。,Sample Problem13,状态压缩,此题乍一看上去好像很简单，因为只要沿着青蛙跳的方向，逐步递推即可。大致代码如下： For i:=1 To L+t-1 Do （仔细想想为什么？） For j:=s To t Do If i这个位子有石头 Then If fifi-j+1 Then fi:=fi-j+1 Else If fifi-j Then fi:=fi-j; 但是有个地方我们忽略了，那就是数据规模。L最大有109，第一个For就已经无法承受庞大的时间限制和空间限制了。所以，这种方法需要进行改进。而改进的方法，就是状态压缩。,状态压缩,我们可以发现题目的一个玄机：虽然L很大，但是M却很小，也就是说：,石子很稀疏,石子稀疏对我们解题有什么帮助呢？我们来看一下下面的推断：,第一种情况： 当s=t时，很简单，青蛙踩到的石头肯定是s的倍数，那么只要统计一下所有石子中有多少是s的倍数，输出即可。,第二种情况：st 我们先来看一组数据。s=4，t=5。,从数据中我们看到，12以后的点全部都是可以到达的了。如果s=4，t=5，在一段100000的距离中没有石头，其实12以后的点都是不用递推就知道肯定能到达的。那么我们用原始的方法做就会浪费很大的资源。 所以当s=4，t=5时，如果一段没有石头的区间长度在4*5=20以外，那么我们只要递推前20就可以了，因为20后面的情况是一样的（仔细想想为什么？）。,状态压缩,假设s=3，t=5，那么11=3+4+4就也可以到达了。所以，只有当t=s+1时，连续的点的起始位置才能尽量后面。最坏情况就是s=9，t=10了（仔细想想为什么？）。 跟前面的s=4，t=5的情况一样，其实s=9，t=10时只要一段没有石头的区间长度在90之外，我们都把它当做90对待就可以了。 因此，我们每次对于一段没有石头的区间长度为x，如果xt(t-1)时，我们就把它当做t(t-1)处理。这样，最大的复杂度就是t(t-1)*（石头个数+1）=90*101=9090，比之前的复杂度大大降低。 这种方法叫状态压缩，我们这题用的方法叫离散 化。至此，过河完美AC！,状态压缩,Sample Problem14,数的划分（NOIp2001） 【问题描述】 将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。 1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。 【输入】 n，k (6n=200，2=k=6) 【输出】 一个整数，即不同的分法。 【样例】 输入： 7 3 输出： 4 四种分法为：1，1，5；1，2，4；1，3，3；2，2，3；,数学递推,应该明确这是一道数学题，数学题往往有明显或暗藏的规律可以快速求得解。在NOIp中数学递推题并不常见，但不能排除它出现的可能性。对于这类问题，我们不能盲目找规律，而要细细寻找每个状态之间的内在联系，从而一步一步求得最终要求的答案。此类问题一般要用到数学公式、数学证明、方程变形、极端化等思想，根据题目的不同适当选取方法。 根据前面讲的，有几个枚举量我们就设几个状态，这道题目明显n和k都是枚举量，要求的几种方案是值，因此建立起递推状态：fi,j表示将i分成j份的方案数。 接下来就是写出状态转移方程了，一旦状态转移方程写出，那么fi,j就可以由fx,y等其他状态得来，因为得到最后我们要求得fn,k。,数学递推,数学递推,我们先来看一下f10,4的几种分割方法，如图：可以看见10=1+1+3+5=1+2+3+4=2+2+3+3。乍一看我们没发现什么规律，但是这些分割方法都有一个共同点：,每种分割方法所分割 出来的小整数都=1!,因为不允许出 现10=0+10这 种分割，所以,数学递推,有了这个性质，我们来尝试下面的操作：将所有小整数都减去1。,这样，f10,4就被改成了f6,2、f6,3、f6,4等小状态。通过类推，小状态可以分成更小的状态。,一般地，fi,j就可以分成fi-j,1、fi-j,2、fi-j,3等小状态，而fi,j的种数就是小状态的总合。,fi,j:=fi-j,1+fi-j,2+fi-j,3+fi-j,j-1+fi-j,j;,数学递推,知道了递推公式，我们就可以推得fn,k。 For i:=1 To n Do For j:=1 To k Do If i=j Then For t:=1 To j Do fi,j:=fi,j+fi-j,t; 时间复杂度是你n*k2的。虽然可以轻松过这题，但如果n=50000，k=200，这样的方法就超时了。所以我们要精益求精：这题还有O(n*k)的方法。 观察下面的变形：,fi,j:=fi-j,1+fi-j,2+fi-j,j;,数学递推,fi-1,j-1:=f(i-1)-(j-1),1+f(i-1)-(j-1),2f(i-1)-(j-1),j-1,=fi-j,1+fi-j,2+fi-j,j-1;, fi,j:=fi-j,1+fi-j,2+fi-j,j-1+fi-j,j,=fi-1,j-1+fi-j,j;,这样，递推就成了n*k的了,For i:=1 To n Do For j:=1 To k Do If i=j Then fi,j:=fi-1,j-1+fi-j,j;,最后加点预处理，此题完美就AC了！ 反思：解决此类题目，必先学好数学！,Sample Problem15,加分二叉树（NOIp2003） 【问题描述】 设一个n个节点的二