题解 P2546 【天赋树】

kkksc03 · 2015-10-17 21:59:38 · 题解

读入数据时把二叉树建好：第一个孩子作为父节点的左子树，其它孩子作为第一个孩子的右子树。

F（x，y）：表示节点x取y天赋的最高学分，则

F（x，y）＝max（f（x.l,k-s[j]）+x.v[j]+f(x.r,y-k)）k=0,1,..y ,j=1,2..直到s[j]<=k，双重循环

f（x.l,k-s[j]）+x.vj :表示选了技能x,左孩子选k-s[j]个技能点,共k个技能点。

f (x.r,y-k)表示右孩子只能选y-k技能点。

节点－1表示空节点，0是根节点，1—n是n门可选技能的节点.